mersenneforum.org > Math Constructing a sieve for trial factors
 Register FAQ Search Today's Posts Mark Forums Read

 2007-12-06, 14:42 #1 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts Constructing a sieve for trial factors The kth bit represents 2kp+1. I want to eliminate all multiples of a prime x (x<2p). For what k (
2007-12-06, 14:51   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts

Quote:
 Originally Posted by davieddy The kth bit represents 2kp+1. I want to eliminate all multiples of a prime x (x<2p). For what k (
Elementary modular arithmetic. For fixed p, just solve 2kp+1 = 0 mod x for
k. WTP???????

What could be simpler?? Didn't they teach you how to formulate and solve
simple equations (in this case a modular equation) when you were in
high school???? If they didn't, then I suggest that you go back and learn
how to do so before proceeding further.

2007-12-06, 15:36   #3
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by R.D. Silverman Elementary modular arithmetic. For fixed p, just solve 2kp+1 = 0 mod x for k. WTP??????? What could be simpler?? Didn't they teach you how to formulate and solve simple equations (in this case a modular equation) when you were in high school???? If they didn't, then I suggest that you go back and learn how to do so before proceeding further.
I wish I could

David

2007-12-06, 16:42   #4
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by R.D. Silverman Elementary modular arithmetic. For fixed p, just solve 2kp+1 = 0 mod x for k. WTP???????
Assuming WTP = "What's the problem" the question
(I'm well past being embarrassed) is how?

 2007-12-06, 18:27 #5 lavalamp     Oct 2007 Manchester, UK 1,373 Posts I'd calculate 2p mod x first, then store that in a variable (say, "res"). Then loop through the bitmap of ks running the test: Code: if((res * k)%x == 1){ flip k bit to 0; } Is that what you mean by how? Last fiddled with by lavalamp on 2007-12-06 at 18:37
 2007-12-06, 18:30 #6 axn     Jun 2003 34·67 Posts 2kp+1 == 0 (mod x) ==> 2kp == -1 ==> k == -1*(2p)^-1 (mod x) Here ^-1 means modular inverse (use Extended Euclidean algorithm for that)
2007-12-06, 19:05   #7
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by lavalamp I'd calculate 2p mod x first, then store that in a variable (say, "res"). Then loop through the bitmap of ks running the test: Code: if((res * k)%x == 1){ flip k bit to 0; } Is that what you mean by how?
Without thinking, this sounds like roughly what I did.
Is there anything simpler?

Last fiddled with by davieddy on 2007-12-06 at 19:08

2007-12-06, 19:11   #8
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by axn1 2kp+1 == 0 (mod x) ==> 2kp == -1 ==> k == -1*(2p)^-1 (mod x) Here ^-1 means modular inverse (use Extended Euclidean algorithm for that)
THX I'll look into this

2007-12-06, 19:41   #9
m_f_h

Feb 2007

24×33 Posts

Quote:
 Originally Posted by lavalamp I'd calculate 2p mod x first, then store that in a variable (say, "res"). Then loop through the bitmap of ks running the test: Code: if((res * k)%x == 1){ flip k bit to 0; } Is that what you mean by how?
I'm willing to give an extract of a basic lecture on modular arithmetic:
Note that if x is prime then Z/xZ is a field and thus there is only one k-value such that 2kp+1=0 [mod x], namely k=-(2p)^-1 [mod x].

Now if you don't want to compute this (using e.g. the GMP library),
and you prefer the above "trial method", then consider 2 improvements:

Concerning the mod operation, in fact it can be avoided in the above, since each time the sum is increased by a quantity < x :

d := 2p % x
s := 1
for k=1 to (2p+1)/x do
. if (s+=d) >= x then if (s-=x)== 0 then deletebit(k)

to avoid looping over all k values a more intelligent approach would be to check if x is sufficiently small, and then to calculate dk = x\d-1 and ds = dk * d (mod x)
and do k += dk, s += ds (mod x) whenever s became > x.
Now you see that you could then again divide the difference x-s by d,
add that to k and the corresponding multiple of d to s....
see what you get ?

PS: oh I notice I was too slow writing that (had some phone calls...) and some partial information had already been given...

Last fiddled with by m_f_h on 2007-12-06 at 19:43

2007-12-06, 19:45   #10
lavalamp

Oct 2007
Manchester, UK

1,373 Posts

Oops, slight correction.
Quote:
 Originally Posted by lavalamp I'd calculate 2p mod x first, then store that in a variable (say, "res"). Then loop through the bitmap of ks running the test: Code: if((res * k)%x == x-1){ flip k bit to 0; } Is that what you mean by how?
Though actually it'd probably just be easier to leave the 1 where it was.
Code:
flip k bit to (((res * k +1)%x == 0)?0:1);

2007-12-06, 20:06   #11
m_f_h

Feb 2007

24×33 Posts

Quote:
 Originally Posted by lavalamp Oops, slight correction.Though actually it'd probably just be easier to leave the 1 where it was. Code: flip k bit to (((res * k +1)%x == 0)?0:1);
no that's not good : only flip to 0. (might have another x as divisor for that k).

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Conjectures 'R Us 95 2017-07-04 13:37 tha Software 24 2014-06-10 23:31 CRGreathouse Math 7 2009-10-22 18:36 lfm Math 15 2009-04-07 11:20 mdettweiler Software 16 2009-03-08 02:06

All times are UTC. The time now is 09:41.

Thu Dec 1 09:41:23 UTC 2022 up 105 days, 7:09, 0 users, load averages: 0.45, 0.68, 0.79