mersenneforum.org Does NewPGen have a bug?
 Register FAQ Search Today's Posts Mark Forums Read

 2008-12-09, 23:00 #1 MooooMoo Apprentice Crank     Mar 2006 11·41 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-09, 23:15   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

23×3×59 Posts

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.

2008-12-09, 23:23   #3
MooooMoo
Apprentice Crank

Mar 2006

7038 Posts

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

 2008-12-09, 23:38 #4 MooooMoo Apprentice Crank     Mar 2006 11×41 Posts 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
 2008-12-10, 00:48 #5 Kosmaj     Nov 2003 E2616 Posts 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
2008-12-10, 03:13   #6
rogue

"Mark"
Apr 2003
Between here and the

2·3,001 Posts

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.

2008-12-10, 03:58   #7
MooooMoo
Apprentice Crank

Mar 2006

11·41 Posts

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.

2008-12-10, 04:54   #8
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

141418 Posts

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.

 2008-12-10, 07:04 #9 gd_barnes     May 2007 Kansas; USA 1023910 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.
2008-12-10, 19:13   #10
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

10110011011112 Posts

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

2008-12-10, 19:47   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

58816 Posts

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 Cybertronic Factoring 0 2014-03-22 10:07 pepi37 Software 12 2013-12-25 18:59 roger Information & Answers 0 2007-04-04 22:38 Cruelty Riesel Prime Search 3 2006-02-15 05:15 Zenmastur Software 4 2003-08-02 19:43

All times are UTC. The time now is 21:42.

Tue Nov 24 21:42:17 UTC 2020 up 75 days, 18:53, 4 users, load averages: 3.58, 3.24, 3.19