- 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. - Milton,

Your first paragraph is very helpful. Your second paragraph has an

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:>

unsubscribe@yahoogroups.com

> 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 at earthlink.net

> miltbrown@e...

>

>

> > [Original Message]

> > From: richard_heylen <rick.heylen@m...>

> > To: <primenumbers@yahoogroups.com>

> > 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-

> > The Prime Pages : http://www.primepages.org/

> >

> >

> > Yahoo! Groups Links

> >

> >

> >

> >