 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

Nov 2003

25×233 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

647410 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 London, UK 24218 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 10010000110112 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
London, UK

1,297 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).   Thread Tools Show Printable Version Email this Page 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 07:15.

Tue Jul 14 07:15:11 UTC 2020 up 111 days, 4:48, 0 users, load averages: 1.89, 1.92, 1.77 