Mathematica 2.0 for SPARC
Copyright 1988-91 Wolfram Research, Inc.
 -- Terminal graphics initialized -- 

In[1]:= <<Numbers.m

Quotient::shdw: Warning: Symbol Quotient appears in multiple contexts 
    {Numbers`, System`}; definitions in context Numbers`
     may shadow or be shadowed by other definitions.
Package Numbers` loaded
0.466667 Second

In[2]:= PeanoMultiplication[m_Integer,n_Integer?NonNegative] realizes m * n by 
   m+m+...+m, n times.

In[2]:=                                           PeanoMultiplication[2, 1000]
0.816667 Second

Out[2]= 2000

In[3]:= PeasantMultiplication[m_Integer,n_Integer?Positive] realizes m * n by  the
   "Russian peasant" method, i.e., by binary exponentiation.

In[3]:=                                               PeasantMultiplication[2, 10000]
0.0333333 Second

Out[3]= 20000

In[4]:= BinaryExponentiation[m_, n_Integer?Positive] realizes m^n by binary 
   exponentiation using the Horner evaluation of n in binary.

In[4]:=                                             BinaryExponentiation[10, 100]
0.0166667 Second

Out[4]= 10000000000000000000000000000000000000000000000000000000000000000000000\
 
>    000000000000000000000000000000

In[5]:= GenericExponentiation[m_, n_Integer?Positive, binop_:Times] realizes m o m o...o
   m,  n times, by binary "exponentiation" using Horner evaluation of n,  where
   o is an associative binary function passed in the binop argument.

In[5]:=                                               op1[x_, y_]:= x + y
0.0166667 Second

In[6]:= GenericExponentiation[2, 10000, op1]
0.05 Second

Out[6]= 20000

In[7]:= op2[x_, y_]:= x * y
0. Second

In[8]:= GenericExponentiation[10, 100, op2]
0.0333333 Second

Out[8]= 10000000000000000000000000000000000000000000000000000000000000000000000\
 
>    000000000000000000000000000000

In[9]:= (* This example exhibits the little Fermat theorem
on fairly large primes or composites (50 digits) *)\
Num = FindPrime[10^50]
18.8833 Second

Out[9]= 100000000000000000000000000000000000000000000000151

In[10]:= op3[x_, y_]:= Mod[x * y, Num]
0. Second

In[11]:= GenericExponentiation[3, Num-1, op3]
0.85 Second

Out[11]= 1

In[12]:= (* Reset P to a composite with large prime factors *)\
Num = FindPrime[10^20] * FindPrime[10^30]
4.66667 Second

Out[12]= 100000000000000000039000000005700000000000000002223

In[13]:= GenericExponentiation[3, Num-1, op3]
0.866667 Second

Out[13]= 2171510387310755753005490004371789579894995374964

In[14]:= FermatPrimeQ[p_Integer?Positive] is a primality test for p based on  Fermat's
   little theorem.

In[14]:= (* This idea is the basis of the Fermat primality test *)\
                       (* This idea is the basis of the Fermat primality test *)\
              (* It fails on so-called Carmichael numbers *)\
CN = 43 * 3361 * 3907
0. Second

Out[14]= 564651361

In[15]:= FermatPrimeQ[CN]
0.283333 Second

Out[15]= True

In[16]:= PrimeQ[CN]
0. Second

Out[16]= False

In[17]:=