mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2008-12-09, 23:00   #1
MooooMoo
Apprentice Crank
 
MooooMoo's Avatar
 
Mar 2006

2·227 Posts
Default Does NewPGen have a bug?

I was sieving k=173 from n=1M to n=2M, and I found this message by NewPGen:

p=2215115304221 divides n=1798220.

However 2,215,115,304,221 is composite (that number is 8627 * 256765423), so that message should not have popped up. Why didn't NewPGen remove n=1798220 when it was at p=8627 or at p=256765423?

In case anyone's wondering, I was using NewPGen version 2.82 on a Pentium 4 computer. The problem also appears on another Pentium 4 machine, so I'm pretty sure it's not a hardware problem.

Last fiddled with by MooooMoo on 2008-12-09 at 23:05 Reason: typo :(
MooooMoo is offline   Reply With Quote
Old 2008-12-09, 23:15   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7·191 Posts
Default

Quote:
Originally Posted by MooooMoo View Post
I was sieving k=173 from n=1M to n=2M, and I found this message by NewPGen:

p=2215115304221 divides n=1798220.

However 2,215,115,304,221 is composite (that number is 8627 * 256765423), so that message should not have popped up. Why didn't NewPGen remove n=1798220 when it was at p=8627 or at p=256765423?

In case anyone's wondering, I was using NewPGen version 2.82 on a Pentium 4 computer. The problem also appears on another Pentium 4 machine, so I'm pretty sure it's not a hardware problem.
k*2^n-1 isn't divisible by your p.
R. Gerbicz is offline   Reply With Quote
Old 2008-12-09, 23:23   #3
MooooMoo
Apprentice Crank
 
MooooMoo's Avatar
 
Mar 2006

2×227 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
k*2^n-1 isn't divisible by your p.
I'm pretty sure it is. I created another test file, clicked "Verify results", and this is the exact line, copy and pasted from NewPGen:

15:21:32 72942 n's remaining. p=2215115304211 divides n=1798220
MooooMoo is offline   Reply With Quote
Old 2008-12-09, 23:38   #4
MooooMoo
Apprentice Crank
 
MooooMoo's Avatar
 
Mar 2006

2·227 Posts
Default

Here's the test file that I used, you can try it for yourself to see that p=2215115304211 really does divide n=1798220:

Code:
2215115300000:M:0:2:258
173 1798016
173 1798038
173 1798060
173 1798064
173 1798068
173 1798080
173 1798096
173 1798098
173 1798130
173 1798134
173 1798172
173 1798196
173 1798212
173 1798220
173 1798236
173 1798254
173 1798264
173 1798274
173 1798320
173 1798344
173 1798348
173 1798350
173 1798382
173 1798386
173 1798400
173 1798420
173 1798428
173 1798436
173 1798448
173 1798464
173 1798528
173 1798536
173 1798542
173 1798562
173 1798576
173 1798614
173 1798628
173 1798652
173 1798656
173 1798668
173 1798684
173 1798696
173 1798704
173 1798718
173 1798736
173 1798742
173 1798768
173 1798782
173 1798812
173 1798854
173 1798898
173 1798920
173 1798924
173 1798956
MooooMoo is offline   Reply With Quote
Old 2008-12-10, 00:48   #5
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2·1,811 Posts
Default

In your post #1 you mentioned p1=2215115304221.
In your post #3 you mentioned p2=2215115304211.
Observe that p1 != p2.

PARI says:
Code:
gp > factorint(p1)
[8627 1]
[256765423 1]         // p1 is composite

gp > factorint(p2)
[2215115304211 1]     // p2 is prime

(09:46) gp > p1-p2
%15 = 10              //  p1 != p2

gp> c=173*2^1798220-1
gp > c%p1
%16 = 1232127380929          // p1 is not a factor of c
gp > c%p2
%17 = 0                      // but p2 is!

Last fiddled with by Kosmaj on 2008-12-10 at 00:54
Kosmaj is offline   Reply With Quote
Old 2008-12-10, 03:13   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

164516 Posts
Default

Quote:
Originally Posted by MooooMoo View Post
I was sieving k=173 from n=1M to n=2M, and I found this message by NewPGen:

p=2215115304221 divides n=1798220.

However 2,215,115,304,221 is composite (that number is 8627 * 256765423), so that message should not have popped up. Why didn't NewPGen remove n=1798220 when it was at p=8627 or at p=256765423?

In case anyone's wondering, I was using NewPGen version 2.82 on a Pentium 4 computer. The problem also appears on another Pentium 4 machine, so I'm pretty sure it's not a hardware problem.
Why are you using NewPGen? sr2sieve would be much faster.
rogue is online now   Reply With Quote
Old 2008-12-10, 03:58   #7
MooooMoo
Apprentice Crank
 
MooooMoo's Avatar
 
Mar 2006

2·227 Posts
Default

Quote:
Originally Posted by Kosmaj View Post
In your post #1 you mentioned p1=2215115304221.
In your post #3 you mentioned p2=2215115304211.
Observe that p1 != p2.
Oops! That's where my problem was

Thanks for pointing it out.
MooooMoo is offline   Reply With Quote
Old 2008-12-10, 04:54   #8
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

141518 Posts
Default

Quote:
Originally Posted by rogue View Post
Why are you using NewPGen? sr2sieve would be much faster.
Indeed. And for one individual k (like you're doing with NewPGen) sr1sieve would be yet even faster.
mdettweiler is offline   Reply With Quote
Old 2008-12-10, 07:04   #9
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

34×53 Posts
Default

Actually, sr1sieve would be the fastest for one OR two k's. For two k's, just run two instances of sr1sieve, which will eat less CPU time than one instance of sr2sieve.
gd_barnes is offline   Reply With Quote
Old 2008-12-10, 19:13   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

22·5·283 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
Actually, sr1sieve would be the fastest for one OR two k's. For two k's, just run two instances of sr1sieve, which will eat less CPU time than one instance of sr2sieve.
what is the crossover point is it 3 ks or more or does it depend on the size of the k or something else
henryzz is offline   Reply With Quote
Old 2008-12-10, 19:47   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7×191 Posts
Default

Quote:
Originally Posted by MooooMoo View Post
I'm pretty sure it is. I created another test file, clicked "Verify results", and this is the exact line, copy and pasted from NewPGen:

15:21:32 72942 n's remaining. p=2215115304211 divides n=1798220
Quote:
Originally Posted by Kosmaj View Post
gp> c=173*2^1798220-1
gp > c%p1
[/CODE]
This tells me that you have got 0 knowledge in calculating in rings. How would you calculate say b^n mod p, where:
Code:
b=5684341886080801486968994140701
n=2481892977737648921240994084183
p=3433683820292512484657849089373
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NewPgen Cybertronic Factoring 0 2014-03-22 10:07
NewPgen question pepi37 Software 12 2013-12-25 18:59
NewPGen k value problem roger Information & Answers 0 2007-04-04 22:38
NewPGen reliability Cruelty Riesel Prime Search 3 2006-02-15 05:15
Problem with Newpgen Zenmastur Software 4 2003-08-02 19:43

All times are UTC. The time now is 01:39.

Thu May 28 01:39:31 UTC 2020 up 63 days, 23:12, 1 user, load averages: 1.89, 2.03, 2.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.