   # Questions and Challenges

Here are some questions to challenge you. I'll post solutions to the questions, along with the names of the submitters, as they are received.

1. Given that

N = 25935464462421628593496082345694765993369684770886032029356695745574501933812519759821423376004840771142910603669551684861946624499543914119801762670446649484275171537355700166319

is a product of THREE distinct prime factors and that

phi(N) = 25935464462421628593496082345694765993369684770882304374952561718902566336903637125240922205125416950563057772616264896244471976456056521865462779015533433360596999085134161930880

(Here phi(N) is Euler's phi-function evaluated on N), find the factorization of N.

(A practical hint: it is a good idea to use the cut-and-paste feature of your web browser to paste the huge numbers N and phi(N) directly into your computer application.)

Solution: Two people succeeded in sending me the factorization: Andrew Ladd and someone who prefers to remain unnamed.

The solution is to exploit an idea that was explicit in the primality test based on Fermat's little theorem, and in the Miller-Rabin primality test (as explained in class, and in Nevena's lecture).

The point is that the order of any element a in (Z/NZ)* must divide f=phi(N), and hence

af=1, (mod N)

Following Nevena's notations and writing f = 2st with t odd, one finds that the first term in the sequence (taken modulo N)

af, af/2, ..., at

which is not equal to 1 is congruent to either 1 or -1 modulo each of the three prime factors p, q and r. Call this term U. It follows that

N = gcd(U-1,N) gcd(U+1,N),

and this factorization is non-trivial precisely when U is not equal to -1 mod N. In practice, this happens quite often (how often??) and so one has an extremeley efficient probabilistic algorithm for factoring N. Note that the knowledge of Phi(N) is essential for this! One sees that a fast algorithm for computing Phi(N) (or the order of a in (Z/Nz)*) yields a fast factorization algorithm. This is one of the key facts used in quantum factorization, as we learned in Sebastian's lecture on Shor's quantum factorization algorithm.

The law of quadratic reciprocity reveals that the question of whether the quadratic equation
X2-q = 0
has a solution modulo a prime p can be expressed as a simple congruence condition on the prime p. Are there similar patterns for higher-degree polynomials? Try your hands at this question by examining the two cubic polynomials

x3 -2,
X3 + x2 - 2 x -1

Make a table giving the shape of the factorization of these two polynomoials, modulo the first few primes (up to 100, say). Do you detect any patterns? Try coming up with some conjectures.