## Question on power residues...

Expand Messages
• Hello everyone, I was wondering if there was a way to use power residues to factor numbers. Let me give an example: Lets say we happen to know that: 2^23 ==
Message 1 of 6 , Jun 2 11:20 AM
Hello everyone,

I was wondering if there was a way to use power residues to factor numbers.
Let me give an example:
Lets say we happen to know that:
2^23 == 536 mod 1071
2^695 == 536 mod 1071
2^71 == 536 mod 1071

I was wondering if there was a way we could use any of the above
information to factor the number 1071. I know 1071 = 3*3*7*17, but I want
to develop a general algorithm, and in order to do so I have to figure out
this part first.

I know that gcd(x, 1071) = 1071
[where x = {2^71 - 2^23, 2^695 - 2^71, 2^695 - 2^23}] so that doesn't give
us any useful information. Taking the first x, 2^71 - 2^23, we could
divide out 2^23 and get 2^48-1. After this we would have:
2^48 == 1 mod 1071.
Could we use this info to somehow factor the number?

Also, something I just noticed, can we use the exponents in the gcd to get
factors? Because:
gcd(71 - 23, 1071) = 3
gcd(695 - 71, 1071) = 3
gcd(695 - 23, 1071) = 21
I'm not necessarily looking for prime factors, just any factor will do.
Will this property with the exponents always hold whenever we have
congruences that are equal. Thanks for any info.

-David C.
• ... numbers. ... From this we know that 2^48 == 1 mod 1071 and I believe that the vast majority of the time, once you know the non-trivial order of any number
Message 2 of 6 , Jun 7 6:27 PM
--- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
wrote:
> Hello everyone,
>
> I was wondering if there was a way to use power residues to factor
numbers.
> Let me give an example:
> Lets say we happen to know that:
> 2^23 == 536 mod 1071
> 2^71 == 536 mod 1071

From this we know that 2^48 == 1 mod 1071 and I believe that the vast
majority of the time, once you know the non-trivial order of any
number modulo a composite then the composite is easily factored.

I'm not sure that this result is completely in the bag in the cases
where you know the highly composite order of some base to which the
number is a strong psuedoprime. For instance, you may know that
2 ^ 242 == 1 mod 2047 but gcd((2^121-1),2047) does not give a factor.
In my current sleep-deprived state, it's not clear to me what the
best way is to proceed in this case in general.

Richard Heylen

Meijer, A. R. "Groups, Factoring, and Cryptography." Math. Mag. 69,
103-109, 1996.
• ... Yeah, it looks like this method will not work when the numbers is of the form ((2^prime) - 1). However, this may be the only class of numbers that this
Message 3 of 6 , Jun 8 1:35 AM
richard_heylen wrote:
>
> David Cleaver wrote:
> > Hello everyone,
> >
> > I was wondering if there was a way to use power residues to factor
> numbers.
> > Let me give an example:
> > Lets say we happen to know that:
> > 2^23 == 536 mod 1071
> > 2^71 == 536 mod 1071
>
> > From this we know that 2^48 == 1 mod 1071 and I believe that the vast
> > majority of the time, once you know the non-trivial order of any
> > number modulo a composite then the composite is easily factored.
>
> I'm not sure that this result is completely in the bag in the cases
> where you know the highly composite order of some base to which the
> number is a strong psuedoprime. For instance, you may know that
> 2 ^ 242 == 1 mod 2047 but gcd((2^121-1),2047) does not give a factor.
> In my current sleep-deprived state, it's not clear to me what the
> best way is to proceed in this case in general.
>
> Richard Heylen
>
> Meijer, A. R. "Groups, Factoring, and Cryptography." Math. Mag. 69,
> 103-109, 1996.

Yeah, it looks like this method will not work when the numbers is of the
form ((2^prime) - 1). However, this may be the only class of numbers that
this method is unnable to factor. If you can think of any other numbers
that might have this property, or if you know of any numbers that can never
be factored by the pollard-rho algorithm, please let me know. Thanks for

-David C.
• ... As I implied, any strong base 2 psuedoprime will do. So from http://www.research.att.com/cgi- bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262
Message 4 of 6 , Jun 8 5:22 AM
--- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
wrote:
>
> Yeah, it looks like this method will not work
> when the numbers is of the form ((2^prime) - 1).
> However, this may be the only class of numbers
> that this method is unnable to factor. If you
> can think of any other numbers that might have
> this property, or if you know of any numbers that
> can never be factored by the pollard-rho algorithm,

As I implied, any strong base 2 psuedoprime will do.
So from

http://www.research.att.com/cgi-
bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262

2047,3277,4033,4681,8321,15841,29341,42799,49141,52633,
65281,74665,80581,85489,88357,90751,104653,130561,196093,
220729,233017,252601,253241,256999,271951,280601,314821,
357761,390937,458989,476971,486737

Richard Heylen
• Residues for the Powers of Prime numbers are discussed in detail in Elementary Number Theory by Jones and Jones with a separate section on page 135. You
Message 5 of 6 , Jun 8 9:25 AM
Residues for the Powers of Prime numbers are discussed
in detail in "Elementary Number Theory" by Jones and Jones
with a separate section on page 135.

You should look there, instead of suggesting that some new
theory is being developed here.

Milton L. Brown
miltbrown@...

> [Original Message]
> From: richard_heylen <rick.heylen@...>
> Date: 6/8/2004 5:24:23 AM
> Subject: [PrimeNumbers] Re: Question on power residues...
>
> --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
> wrote:
> >
> > Yeah, it looks like this method will not work
> > when the numbers is of the form ((2^prime) - 1).
> > However, this may be the only class of numbers
> > that this method is unnable to factor. If you
> > can think of any other numbers that might have
> > this property, or if you know of any numbers that
> > can never be factored by the pollard-rho algorithm,
> > please let me know. Thanks for your input so far.
>
> As I implied, any strong base 2 psuedoprime will do.
> So from
>
> http://www.research.att.com/cgi-
> bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262
>
> 2047,3277,4033,4681,8321,15841,29341,42799,49141,52633,
> 65281,74665,80581,85489,88357,90751,104653,130561,196093,
> 220729,233017,252601,253241,256999,271951,280601,314821,
> 357761,390937,458989,476971,486737
>
> Richard Heylen
>
>
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
• Milton, Your first paragraph is very helpful. Your second paragraph has an unfortunate condescending tone. I know people are frequently thinking they have
Message 6 of 6 , Jun 8 4:53 PM
Milton,

unfortunate condescending tone. I know people are frequently
thinking they have discovered something new that is 400 years old.
It is great to point them to the earlier work, but I do not want
people to be afraid to post to the list because they might be subtly
ridiculed.

Best regards,

David

--- In primenumbers@yahoogroups.com, "Milton Brown" <miltbrown@e...>
wrote:
>
> Residues for the Powers of Prime numbers are discussed
> in detail in "Elementary Number Theory" by Jones and Jones
> with a separate section on page 135.
>
> You should look there, instead of suggesting that some new
> theory is being developed here.
>
> Milton L. Brown
> miltbrown@e...
>
>
> > [Original Message]
> > From: richard_heylen <rick.heylen@m...>
> > Date: 6/8/2004 5:24:23 AM
> > Subject: [PrimeNumbers] Re: Question on power residues...
> >
> > --- In primenumbers@yahoogroups.com, David Cleaver <wraithx@m...>
> > wrote:
> > >
> > > Yeah, it looks like this method will not work
> > > when the numbers is of the form ((2^prime) - 1).
> > > However, this may be the only class of numbers
> > > that this method is unnable to factor. If you
> > > can think of any other numbers that might have
> > > this property, or if you know of any numbers that
> > > can never be factored by the pollard-rho algorithm,
> > > please let me know. Thanks for your input so far.
> >
> > As I implied, any strong base 2 psuedoprime will do.
> > So from
> >
> > http://www.research.att.com/cgi-
> > bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001262
> >
> > 2047,3277,4033,4681,8321,15841,29341,42799,49141,52633,
> > 65281,74665,80581,85489,88357,90751,104653,130561,196093,
> > 220729,233017,252601,253241,256999,271951,280601,314821,
> > 357761,390937,458989,476971,486737
> >
> > Richard Heylen
> >
> >
> >
> >
> >
> > Unsubscribe by an email to: primenumbers-
unsubscribe@yahoogroups.com
> > The Prime Pages : http://www.primepages.org/
> >
> >