189-346 / 377B: Number Theory
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.)
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
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
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
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 + 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.