Does NewPGen have a bug?

MooooMoo · 2008-12-09, 23:00

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.

R. Gerbicz · 2008-12-09, 23:15

Quote:

Originally Posted by MooooMoo

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.

MooooMoo · 2008-12-09, 23:23

Quote:

Originally Posted by R. Gerbicz

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 · 2008-12-09, 23:38

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

Kosmaj · 2008-12-10, 00:48

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!

rogue · 2008-12-10, 03:13

Quote:

Originally Posted by MooooMoo

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.

MooooMoo · 2008-12-10, 03:58

Quote:

Originally Posted by Kosmaj

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.

mdettweiler · 2008-12-10, 04:54

Quote:

Originally Posted by rogue

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.

gd_barnes · 2008-12-10, 07:04

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.

henryzz · 2008-12-10, 19:13

Quote:

Originally Posted by gd_barnes

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

R. Gerbicz · 2008-12-10, 19:47

Quote:

Originally Posted by MooooMoo

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

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

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

2008-12-09, 23:00	#1
MooooMoo Apprentice Crank Mar 2006 2·227 Posts	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 :(

2008-12-10, 07:04	#9
gd_barnes May 2007 Kansas; USA 2·41·127 Posts	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.