Re: Factoring integers on a classical computer

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/17/05 

Date: 16 Mar 2005 17:51:15 -0800

tchow@lsa.umich.edu wrote:
> In article <1111001652.654406.162030@l41g2000cwc.googlegroups.com>,
> Craig Feinstein <cafeinst@msn.com> wrote:
> >16^3=1 (mod 45)
> >So we have a multiplicative cycle of order 3 in a ring of size 45.
> >Therefore, 3 divides 45.
>
> Trying another example, we find that 6^2 = 1 (mod 7). So we have
> a multiplicative cycle of order 2 in a ring of size 7. Therefore,
> 2 divides 7. Right?
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however
great, will
> never exceed four of those miles of which as many thousand separate
us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New
Sciences

You are absolutely correct, Tim. I am a little rusty on my algebra. The
correct conclusion from my observation is not that 3 divides 45, but
that 3 divides phi(45)=24. Still, doesn't knowing the factors of
phi(45)=(5-1)*(3-1)*3 give enough information that can allow one to
determine the factors of 45=3^2*5 in poly-time?

So perhaps this procedure of simply exponentiating a^(n-1) modulo n in
poly-time still allows one to determine the factors of phi(n)
(regardless of whether Fermat's Little Theorem fails), which can lead
one to the factors of n?

Craig

Quantcast