Order Finding

In the previous notebook we demonstrated that factoring a very large semi prime number n=p q is very difficult and
time consuming. As the number of digits in n grows, the logarithm of the time it took for Mathematica to factor it
seemed to grew in a linear fashion. Alternatively this means that the time spent on the computation grew exponentialy.

This is why RSA encryption is safe. For a sufficiently large n in the public key, no one has computers powerfull enough to
factor it into its two prime component p q.  

There are many schemes for factoring prime numbers (e.g. Euclid's method). One of them (Miller's algorithm) depends on finding the order of a number, so we must first understand this definition.

Consider a positive integer x, so that  x < N where N is another integer. Consider now this
equation

(x^r)  Mod N = 1 

the smallest positive integer r that satisfies the above equation is called the order of x with N.  Here x is called the seed. This is a very hard problem for large N. Let's solve for some r,N.  In Millers algorithm we will be interested only in pairs in which x and N are
co-prime. That is they do not share a common factor or the Greatest Common Divisor (GCD) is one.

Clear[x];
x=2;
Num=49;
GCD[x,Num]

Mod[x^1,Num]

ordertable=Table[Mod[x^i,Num],{i,1,Num-1}]

ListPlot[ordertable,Joined->True]

In using Miller's algorithm we also require r to be an even integer. Using these definitions we note
that the above equation is equivalent to

( (x^r)  - 1 ) Mod N =0

That is N divides into  ( (x^r)  - 1 ). Now we agreed that r should be even, so we can then factor the above
equation as

((x^(r/2))-1) ((x^(r/2))+1) Mod N =0

Lets call  A ≡ ((x^(r/2))-1)  and  B ≡ ((x^(r/2))+1)   and we consider that N is the semi-prime number (the modulus from Alice's public key) .

So N divides the product A B.  If  N divides B i.e.  ((x^(r/2))+1) Mod N =0, we pick a new seed x, and order r until the conditions

((x^(r/2))+1) Mod N ≠ 0

is satisfied.  If that is the case then if ((x^(r/2))-1) Mod N = 0  the above also identity holds.  Or   

(x^(r/2)) Mod N = 1

Now,  we know that r is the smallest integer, by definition, that satisfies the above equation, therefore there is a contradiction.
i.e.   ((x^(r/2))-1) Mod N ≠ 0 also. Thus the only way we can say that

((x^(r/2))-1) ((x^(r/2))+1) Mod N =0  is that  the factors  ((x^(r/2))-1) ((x^(r/2))+1)  comprise the product p q = N where p, q are the prime
factors of N.

Thus, with Miller's algorithm, we find p  and q using the following the prescription

(1)  Choose a seed x for the modulus n
(2)  Find the smallest even interger order i.e.    (x^r)  Mod n = 1   (This is hard)
(3) Make sure that ((x^(r/2))+1) Mod n ≠ 0, if it does go back to step 1 and start over
(4) The prime factors p,q  of n  will be  GCD[((x^(r/2))+1),n],  or GCD[ ((x^(r/2))-1),n]

Let’s check Miller’s algorithm for some special cases.

primes=Table[Prime[x],{x,1,20}]

(* Lets' arbitrary choose two primes, p, q from this list *)

p=primes[[12]]
q=primes[[17]]

nmod=p q

(* so we want to factor nmod, lets proceed with the above prescription *)
(* 1 *)

seed=25
(* check to see if the seed is co-prime with nmod *)
(* if it ins't choose another seed *)
GCD[nmod,seed]

(* solve (x^r)  = 1 Mod n for smallest r, we will do this graphically *)
(* 2 *)

list=Table[Mod[seed^r,nmod],{r,1,100}];

ListPlot[list,Joined->False,PlotRange->All,Filling->Axis,PlotStyle->{Red}]

Mod[seed^r /. r->522,nmod]

(* so graphically we solved this equation and found that r=522 *)
(* we now need to check item (3) is r even ?*)
522/2

(* yes ! good we can proceed *)

Mod[(seed^(r/2)-1) /. r->522,nmod]

(* Good ! good since Mod(x^r/2-1,n) does not equal to zero, we can read off the prime factors *)

factora=GCD[(seed^(r/2)-1) /. r->522,nmod] 
factorb=GCD[(seed^(r/2)+1) /. r->522,nmod]

factora factorb

(* which are the prime factors, p, q given above. *)

Though we can solve the equation

 (x^r) Mod n  = 1 
 
 graphically, we can see already from the example above that this is tedious and not systematic. There is a better
 algorithm by recognizing that the problem  (x^r)  = 1 Mod n is equivalent to solving for the period of
 the function
 
 f(r) = (x^r) Mod n
 
 the period ω is defined as the quantity such that  f(r+ω)=f(r)
 
 Proof.
 
 According to the above definition
 
 f(r+ω) = (x^((r+ω))) Mod n =  ((x^r) Mod n)  (  (x^ω) Mod n )  Mod n = f(r)
 
 therefore   (  (x^ω) Mod n ) = 1  which is the equation we need to solve  QED.

Let’s now try this with a more difficult scenario