--- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:
> What is not yet known is what complexity class factoring
> belongs to.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I see. Thank you Paul, as well as Décio for saving me countless
hours of unnecessarily wasted effort. As I understand it then, the
real problem in this particular case would be to "reverse" the
equations I mentioned so that the a's and b's are solved for in
terms of the bits of the composite number to be factored rather
than the way I show them? In other words, what I need (for
example) is to convert equations like these:

n1 = a1 ^ 1
n2 = a1 ^ b1
(Where n1 and n2 are binary bits of the composite number to be
factored)

Into something like this:

a1 = n1 ^ 1
b1 = n1 ^ n2 ^ 1

I realize this is probably impossible in general, but if it *were*
possible it would show that factoring is in P, right?

Thanks,

Ron

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBQL1FbhpqFjUCnHWBEQJV7ACg4+muUEwxKT/Mwx60WWW2w81Md1IAoO4S
cL/ybm7yzzuaSm/X6gHDco6P
=+2jM
-----END PGP SIGNATURE-----

Greetings,
I have updated (finally!) the tables at the Proth Prime site
(http://www.prothsearch.net/index.html). Sorry for the delay.
Thank you for the support many of you have given over the years.

Regards,
Ray Ballinger

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.

Sorry, what is the purpose of    n1 = a1 ^ 1  and   a1 = n1 ^ 1  ?
Aren't these just  n1 = a1  and  a1 = n1 ?

It would be helpful to explain these, or have your mathematics
thought out more before posting.

Thanks.

Milton L. Brown
miltbrown at earthlink.net
miltbrown@...

----- Original Message -----
From: "Ron" <Yaho6Hb3c@...>
To: <primenumbers@yahoogroups.com>
Sent: Tuesday, June 01, 2004 8:13 PM
Subject: [PrimeNumbers] Re: Boolean algebra solver?


--- In primenumbers@yahoogroups.com, Paul Leyland <pcl@w...> wrote:
> What is not yet known is what complexity class factoring
> belongs to.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I see. Thank you Paul, as well as Décio for saving me countless
hours of unnecessarily wasted effort. As I understand it then, the
real problem in this particular case would be to "reverse" the
equations I mentioned so that the a's and b's are solved for in
terms of the bits of the composite number to be factored rather
than the way I show them? In other words, what I need (for
example) is to convert equations like these:

n1 = a1 ^ 1
n2 = a1 ^ b1
(Where n1 and n2 are binary bits of the composite number to be
factored)

Into something like this:

a1 = n1 ^ 1
b1 = n1 ^ n2 ^ 1

I realize this is probably impossible in general, but if it *were*
possible it would show that factoring is in P, right?

Thanks,

Ron

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBQL1FbhpqFjUCnHWBEQJV7ACg4+muUEwxKT/Mwx60WWW2w81Md1IAoO4S
cL/ybm7yzzuaSm/X6gHDco6P
=+2jM
-----END PGP SIGNATURE-----





Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/


Yahoo! Groups Links

Milton Brown wrote:
>
> Sorry, what is the purpose of    n1 = a1 ^ 1  and   a1 = n1 ^ 1  ?
> Aren't these just  n1 = a1  and  a1 = n1 ?

No they are not.  When he uses the ^ operator, he means the xor (exclusive
or) operator.  If you don't know about the xor operator, here's a quick
tut:
0^0 = 0
0^1 = 1
1^0 = 1
1^1 = 0
So, what n1 = a1 ^ 1 basically means is if a1 is 0 then n1 is 1, and vice
versa.  HTH.

-David C.

>
> It would be helpful to explain these, or have your mathematics
> thought out more before posting.
>
> Thanks.
>
> Milton L. Brown

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Justin asked me for a real life example of how this technique
can be used to find factors, so at the risk of boring everyone
else, I thought I'd post it here on the forum. Here is a sample
Maple code snippet ('#' begins a comment) that illustrates the
problem:

n:= [0,0,1,1,1,1]:  # factor binary 001111 = decimal 15 = 3*5

c1:=a1*b1:
c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):
c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):
c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):
c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):

eqn := {a1+b1 = 1,
a2+a1*b1+b2+c1 = 1,
a2*b1+a1*b2+c2 = 1,
a2*b2+c3+c4 = 0,
c5 = 0};

solve(eqn,{a1,a2,b1,b2});  # <= Maple can't solve this

# But the solution is:

a2:=0: a1:=1:  # a0:=1, so that a= "011" binary = 3 decimal
b2:=1: b1:=0:  # a0:=1, so that b= "101" binary = 5 decimal

# Where a=3 and b=5 are the factors of 15.

Ron Dotson
6/03/2004

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBQL97thpqFjUCnHWBEQIOeQCgpMXLFGkaEsNQ/nshYRRMxNVi3+8An3RQ
20UaohAI3jTT0B9S1XCz0Fj2
=Zgga
-----END PGP SIGNATURE-----

On Thu, 3 Jun 2004, Ron wrote:

>
> n:= [0,0,1,1,1,1]:  # factor binary 001111 = decimal 15 = 3*5
>
> c1:=a1*b1:
> c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):
> c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):
> c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):
> c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):
>
> eqn := {a1+b1 = 1,
> a2+a1*b1+b2+c1 = 1,
> a2*b1+a1*b2+c2 = 1,
> a2*b2+c3+c4 = 0,
> c5 = 0};
>
> solve(eqn,{a1,a2,b1,b2});  # <= Maple can't solve this

Actually one can solve the system eqn  with Maple (in two ways):

First way: (note in this case one has free variables b1,b2,c1,c4 so we
allow them to be any of 0 or 1 and see what works)

Sol:=solve(eqn);
                                        2
   Sol := {c5 = 0, a1 = -b1 + 1, a2 = b1  - b1 - b2 - c1 + 1,

                 3     2
         c2 = -b1  + b1  + 2 b2 b1 + b1 c1 - b1 - b2 + 1,

                    2             2
         c3 = -b2 b1  + b2 b1 + b2  + b2 c1 - b2 - c4, b1 = b1,

         b2 = b2, c1 = c1, c4 = c4}

> for b1 from 0 to 1 do
> for b2 from 0 to 1 do
> for c1 from 0 to 1 do
> for c4 from 0 to 1 do
>   a:=eval(a2*4+a1*2+1,Sol);
>   b:=eval(b2*4+b1*2+1,Sol);
> if a*b = 15 then print(a,b); fi;
> od;
> od;
> od;
> od:




Second way: Us msolve to solve modulo 2. It gives 5 solutions, but it can
pick the one that works: (It may just be luck that this works?) Here's
how:

> eqn := {a1+b1 = 1,
> a2+a1*b1+b2+c1 = 1,
> a2*b1+a1*b2+c2 = 1,
> a2*b2+c3+c4 = 0,
> c5 = 0}:
> Sol:=msolve(eqn,2);

   Sol := {c5 = 0, b1 = 1, a1 = 0, c2 = 1, c1 = 1, a2 = 0, b2 = 0,

         c3 = c4}, {c5 = 0, b1 = 1, a1 = 0, c2 = 1, c1 = 0, b2 = 1,

         a2 = 0, c3 = c4}, {c5 = 0, b1 = 1, a1 = 0, a2 = 1, c1 = 0,

         b2 = 0, c3 = c4, c2 = 0}, {c5 = 0, b1 = 1, a1 = 0, a2 = 1,

         c1 = 1, b2 = 1, c2 = 0, c3 = c4 + 1}, {c5 = 0, a1 = 1, c2 = 1,

         c1 = 1, a2 = 0, b2 = 0, c3 = c4, b1 = 0}

> for i from 1 to nops([Sol]) do
> a:=eval(a2*4+a1*2+1,Sol[i]);
> b:=eval(b2*4+b1*2+1,Sol[i]);
> if a*b = 15 then print(a,b); fi
> od:

                                  5, 3

I'm not sure why we don't also get 3,5 this way.

--Edwin Clark


>
> # But the solution is:
>
> a2:=0: a1:=1:  # a0:=1, so that a= "011" binary = 3 decimal
> b2:=1: b1:=0:  # a0:=1, so that b= "101" binary = 5 decimal
>
> # Where a=3 and b=5 are the factors of 15.
>
> Ron Dotson
> 6/03/2004
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>
>
> iQA/AwUBQL97thpqFjUCnHWBEQIOeQCgpMXLFGkaEsNQ/nshYRRMxNVi3+8An3RQ
> 20UaohAI3jTT0B9S1XCz0Fj2
> =Zgga
> -----END PGP SIGNATURE-----
>
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
> Yahoo! Groups Sponsor
> ADVERTISEMENT
> click here
> [rand=153996665]
>
>
________________________________________________________________________________
> Yahoo! Groups Links
>  *  To visit your group on the web, go to:
>     http://groups.yahoo.com/group/primenumbers/
>      
>  *  To unsubscribe from this group, send an email to:
>     primenumbers-unsubscribe@yahoogroups.com
>      
>  *  Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
>
>

--
---------------------------------------------------------
   W. Edwin Clark, Math Dept, University of South Florida
            http://www.math.usf.edu/~eclark/
---------------------------------------------------------

It has been suggested to me that Chebyshev (I am not sure which one-
  apparently there are many)has a theory that says something like
there is always one prime between n^2 and (n^2+2n).  I cannot find
it, or I don't recognize it when I do find it.  Can anyone tell me if
the theorem is as I stated, and where I can find it documented?
Thanks for any help.
                           Bill

In a message dated 04/06/04 05:54:15 GMT Daylight Time,
billroscarson@... writes:


> It has been suggested to me that Chebyshev (I am not sure which one-
> apparently there are many)has a theory that says something like
> there is always one prime between n^2 and (n^2+2n).  I cannot find
> it, or I don't recognize it when I do find it.  Can anyone tell me if
> the theorem is as I stated, and where I can find it documented?
> Thanks for any help.
>

I think you must be thinking of Bertrand's postulate, which
"is that, for every n > 3, there is a prime p satisfying n < p < 2n-2.
Bertrand verified this for n < 3,000,000 and Tchebychef proved it for all n > 3
in
1850."
[Hardy & Wright (1979), p. 373]

If p[n] is the nth prime number, define
d[n] = p[n+1] - p[n]
Then your statement would be equivalent to the assertion that d[n] <=
2*p[n]^0.5.

This is probably true (for n "sufficiently large"), but has never been proved.
In fact, it is widely conjectured that d[n] < p[n]^0.5 except for a finite
number of cases.

If the Riemann hypothesis is assumed, it is (relatively!) easy to prove that,
if t is any fixed number > 0.5, then d[n] < p[n]^t except for a finite number
of cases.

By 1990 the strongest result unconditionally proved (by Mozzochi in 1986) was
that  this statement is true with t any fixed number > 1051/1921.
[A..E.Ingham "The Distribution of Prime Numbers" (1990)]

Is this the latest state of play, anyone know?

-Mike Oakes



[Non-text portions of this message have been removed]

--- In primenumbers@yahoogroups.com, Edwin Clark <eclark@m...> wrote:
>
> Actually one can solve the system eqn  with Maple (in two ways):
>

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Very perceptive Edwin. I didn't know we had any Maple users
in this group. You are correct that if you copy/paste the
following lines into a Maple worksheet:

c1:=a1*b1:
c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):
c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):
c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):
c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):
eqn := {a1+b1 = 1,
a2+a1*b1+b2+c1 = 1,
a2*b1+a1*b2+c2 = 1,
a2*b2+c3+c4 = 0,
c5 = 0}:
Sol:=msolve(eqn,2);

Maple provides the solutions immediately:
Sol := {a1 = 0, b1 = 1, a2 = 1, b2 = 0},
        {a1 = 1, b1 = 0, a2 = 0, b2 = 1}

I should have used "msolve()" in my example instead of
"solve()." *However*, if you use the actual RSA-640 carry
definitions and equations (all 135MB of them!) instead of the
equations in this simple example, Maple's "msolve()" also fails.
If you don't include the carry definitions it fails immediately,
and if you include them it runs for awhile (hours) and then
terminates with an "Out of Memory" error while trying to expand
the carry definitions (if I recall correctly). If anyone wants
to try it themselves, you can download the carry definition file
(Carries.txt) and the equation file (equ.dat) as a single gzipped
tar file from:
http://snipurl.com/6uqu/rsa640.tar.gz

or as a Windows ZIP file from:
http://snipurl.com/6uqu/rsa640.zip

(They are both about 10MB in size)

To have Maple try to solve them, paste the following
into a Maple worksheet and execute it from the same directory
you unzipped "equ.dat" and "Carries.txt" into:

restart:
print("Reading Equations");
read "equ.dat":
print("Reading Carries");
read "Carries.txt":
print("Solving");
Sol:=msolve(equ,2);

Maybe it will work on a computer that's faster than
mine and has more RAM, but I doubt it. I have
an Athlon 1.1 GHz AMD processor with 1 GB RAM.

Ron Dotson
6/04/2004


-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBQMA8TRpqFjUCnHWBEQJCuACgiJx8iXGukS9pxZpbIsNBtwbRG5gAn29u
PVyC48adMZA1O0PDOq7aJfFL
=ulm/
-----END PGP SIGNATURE-----

Hi Ron,

R> Justin asked me for a real life example of how this technique
R> can be used to find factors, so at the risk of boring everyone
R> else, I thought I'd post it here on the forum. Here is a sample
R> Maple code snippet ('#' begins a comment) that illustrates the
R> problem:

  Thanks Ron. I think I've finally understood the idea of the technique. I
  also understand long-hand multiplication at long last ;)

R> n:= [0,0,1,1,1,1]:  # factor binary 001111 = decimal 15 = 3*5

R> eqn := {a1+b1 = 1,
R> a2+a1*b1+b2+c1 = 1,
R> a2*b1+a1*b2+c2 = 1,
R> a2*b2+c3+c4 = 0,
R> c5 = 0};

  As you know, these equations in the Z(2) field are equivalent to boolean
  expressions. So they can be transformed the following way to eliminate the
  equality:

    lhs == 1  ->  lhs
    lhs == 0  ->  NOT(lhs)  -> lhs+1 (equivalent to NOT using only xor)

  now all the ex-equations can be combined to one with AND (ie multiplication
  in Z(2)) to form one expression:

    (a1+b1) (a2+a1*b1+b2+c1) (a2*b1+a1*b2+c2) (a2*b2+c3+c4+1) (c5+1)

  This can be reduced algebraically and transformed to boolean:

    (a1 && b2 && ! a2 && ! b1) || (a2 && b1 && ! a1 && ! b2)

  Which in effect is indeed your solution:

R> # But the solution is:

R> a2:=0: a1:=1:  # a0:=1, so that a= "011" binary = 3 decimal
R> b2:=1: b1:=0:  # a0:=1, so that b= "101" binary = 5 decimal

R> # Where a=3 and b=5 are the factors of 15.


  I use Mathematica, and am not familiar with Maple, but I suppose it is
  just as capable of these transformations.

  I'm not sure about the practicability though. It already took a few seconds
  to reduce your example expressions (albeit with somewhat straightforward
  and probably not really efficient reduction algorithm).

  But then, what do I know? ;P

--
Justin
ICQ 37456745
AIM jasticle

Hi all,

it was really time to update my list of Cunningham Chain records
which you can find in the file Cunningham_Chain_records.txt
located in "Files > Prime Tables".

Thx to Jens Kruse Andersen for waking me up! ;-)


Regards,
Dirk Augustin

Hi,
Prime numbers written out in english as such

two, three, four, seven, ten, eleven, twelve, fourteen, seventeen, ...
Are blind primes because the have no i's.

My question is can we prove thes primes are infinite?

Certainly blind numbers are infinite.

Cino

Hi cino,

ch> Prime numbers written out in english as such

ch> two, three, four, seven, ten, eleven, twelve, fourteen, seventeen, ...
ch> Are blind primes because the have no i's.

ch> My question is can we prove thes primes are infinite?

  Some of your given examples look rather composite to me, though of course
  blind. :P

--
Justin
ICQ 37456745
AIM jasticle

It depends on the English rules for writing a large number. If one may use
thousand thousand instead of a million then blind primes are infinite.


[Non-text portions of this message have been removed]

Prime has an I in it. There are no blind primes.


[Non-text portions of this message have been removed]

>From: chasag@...
>To: primenumbers@yahoogroups.com
>Subject: Re: [PrimeNumbers] Digest Number 1324
>Date: Mon, 7 Jun 2004 14:56:55 EDT
>
>Prime has an I in it. There are no blind primes.
Hmmm... I didn't see that!
>

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

Theja Kurniawan
Dept of Mathematics
IPEKA Christian School
Phone/Fax: 62 21 5656023 / 24



[Non-text portions of this message have been removed]

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
your input so far.

-David C.

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

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


> [Original Message]
> From: richard_heylen <rick.heylen@...>
> 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-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
> Yahoo! Groups Links
>
>
>
>

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:
>
> 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-
unsubscribe@yahoogroups.com
> > The Prime Pages : http://www.primepages.org/
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >

I have found this new prime conjecture

n is a prime number only when k is a hole number

((2^n)-2)/n = k



Discovered by:
Eduardo Mourey López Negrete
Torreón Coah. Mexico
Torreón Jardin
Lirios 333
27200

If n is a prime number then ((2^n)-2)/n is always an integer. This
follows from Fermats Little Theorem, one of the first things one learns
about in number theory. The converse is false, ie the statement that:

If ((2^n)-2)/n is an integer then n is prime

is not right. For instance, consider n=341 then you get

(2^341 - 2)/341 =
1313633279869679888889995472
4741608669335164206654835981
8181178942157881007634073042
86671514789484550 (one big integer spanning over 4 rows)

which clearly is an integer. However, 341 is not prime.
You can read more about this elementary theorem here:
http://mathworld.wolfram.com/FermatsLittleTheorem.html


Regards,
/m

edmorrey wrote:
> I have found this new prime conjecture
>
> n is a prime number only when k is a hole number
>
> ((2^n)-2)/n = k
>
>
>
> Discovered by:
> Eduardo Mourey López Negrete
> Torreón Coah. Mexico
> Torreón Jardin
> Lirios 333
> 27200
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
> *Yahoo! Groups Sponsor*
> ADVERTISEMENT
>
<http://rd.yahoo.com/SIG=129m9q24q/M=298184.5022502.6152625.3001176/D=groups/S=1\
705083388:HM/EXP=1086885375/A=2164331/R=0/SIG=11eaelai9/*http://www.netflix.com/\
Default?mqso=60183351>
>
>
> ------------------------------------------------------------------------
> *Yahoo! Groups Links*
>
>     * To visit your group on the web, go to:
>       http://groups.yahoo.com/group/primenumbers/
>
>     * To unsubscribe from this group, send an email to:
>       primenumbers-unsubscribe@yahoogroups.com
>       <mailto:primenumbers-unsubscribe@yahoogroups.com?subject=Unsubscribe>
>
>     * Your use of Yahoo! Groups is subject to the Yahoo! Terms of
>       Service <http://docs.yahoo.com/info/terms/>.
>
>

> I have found this new prime conjecture
>
> n is a prime number only when k is a hole number
>
> ((2^n)-2)/n = k

Hi,

this is the fermat-test for base 2:

n is prime only if 2^(n-1) = 1 mod (n) ==> (2^(n-1)-1)/n is an integer
==> 2*(2^(n-1)-1)/n=(2^n-2)/n is an integer.


Cyrix

I believe Fermat "discovered" this centuries ago (or possibly even
Euclid?).  This is simply  a Fermat-2 PRP test.  Yes, all primes
certainly ARE shown by k being a whole number (i.e. ((2^n)-2)%n == 0)

This can be extened for any "base".  So ((2^n)-2)%n==0 implies
Fermat PRP in base 2, and ((b^n)-b)%n==0 implies Fermat PRP in base
b.  NOTE these are still just "probably" prime.  For your PRP-2
below, 341 is the smallest composite that "passes".  However, as
you pointed out, there will be NO primes that fail this test.

This method is most "commonly" used in modular space.   Computing
whether ((2^329018309280127)-2)/329018309280127 is a whole number
(without using modular methods), is a VERY hard thing to do, since
2^329018309280127 is a number larger than any "current" computer can
handle.   However, computing (2^329018309280127)%329018309280127
then subtracting 2, and checking if the result is zero, can be done
on binary computers in a fraction of a second, by continually
reducing the intermediate results mod n (or 329018309280127 in this
case).

It is always fun to "discover" something, however, when I have done
so in the past, I usually (always in my case) find out that someone,
(like Euclid, Fermat, Erdos, Euler, Newton, Pascal, ...) beat me to
it long long ago.  However, I still keep trying ;)

Jim.

--- In primenumbers@yahoogroups.com, "edmorrey" <edmorrey@y...> wrote:
> I have found this new prime conjecture
>
> n is a prime number only when k is a hole number
>
> ((2^n)-2)/n = k
>
>
>
> Discovered by:
> Eduardo Mourey López Negrete
> Torreón Coah. Mexico
> Torreón Jardin
> Lirios 333
> 27200

http://www.math.purdue.edu/ftp_pub/branges/apology.pdf


Jose Brox
http://espanol.groups.yahoo.com/group/Telecomunicacion/
(www.brox.tk)
ambroxius@...
MSN Messenger: artifex_ad_infinitum@...



[Non-text portions of this message have been removed]

Jose Ramón Brox wrote:
>
> http://www.math.purdue.edu/ftp_pub/branges/apology.pdf
>
> Jose Brox
> http://espanol.groups.yahoo.com/group/Telecomunicacion/
> (www.brox.tk)
> ambroxius@...
> MSN Messenger: artifex_ad_infinitum@...

It looks like the apology is separate from the proof.  The apology is 23
pages and gives a lot of personal history and other mathematical details
which I don't understand.  But, as I saw someone point out, on his page
located at:
http://www.math.purdue.edu/~branges/
It looks like the actual proof is the "Riemann zeta functions" pdf file,
3rd link down, on that page.  It weighs in at a hefty 124 pages.  The
direct link to the pdf is here:
http://www.math.purdue.edu/ftp_pub/branges/riemannzeta.pdf
Just thought I'd clear that up because I know originally it confused me.

-David C.

Hi:

     I found a simple sieve method, somewhat similar
to the sieve of Erathostenes, which allows to directly
sieve twin primes. I would like to know, if this method
is already known in the literature and if a proof for
it exists.

You can find the ps file under the url:

http://www.rzuser.uni-heidelberg.de/~aernst/sieve1.ps

Andreas


--
"Sie haben neue Mails!" - Die GMX Toolbar informiert Sie beim Surfen!
Jetzt aktivieren unter http://www.gmx.net/info