mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-12-06, 14:42   #1
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default 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 (<x) is 2kp+1 a multiple of x?
Is there a clever way of answering(/programming) this?

David

Last fiddled with by davieddy on 2007-12-06 at 15:14
davieddy is offline   Reply With Quote
Old 2007-12-06, 14:51   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by davieddy View Post
The kth bit represents 2kp+1.
I want to eliminate all multiples of a prime x (x<2p).
For what k (<x) is 2kp+1 a multiple of x?
Is there a clever way of answering this?

David
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-12-06, 15:36   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

647410 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
davieddy is offline   Reply With Quote
Old 2007-12-06, 16:42   #4
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
davieddy is offline   Reply With Quote
Old 2007-12-06, 18:27   #5
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

24218 Posts
Default

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
lavalamp is online now   Reply With Quote
Old 2007-12-06, 18:30   #6
axn
 
axn's Avatar
 
Jun 2003

10010000110112 Posts
Default

2kp+1 == 0 (mod x)
==> 2kp == -1
==> k == -1*(2p)^-1 (mod x)

Here ^-1 means modular inverse (use Extended Euclidean algorithm for that)
axn is offline   Reply With Quote
Old 2007-12-06, 19:05   #7
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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
davieddy is offline   Reply With Quote
Old 2007-12-06, 19:11   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by axn1 View Post
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
davieddy is offline   Reply With Quote
Old 2007-12-06, 19:41   #9
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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
m_f_h is offline   Reply With Quote
Old 2007-12-06, 19:45   #10
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

1,297 Posts
Default

Oops, slight correction.
Quote:
Originally Posted by lavalamp View Post
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);
lavalamp is online now   Reply With Quote
Old 2007-12-06, 20:06   #11
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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).
m_f_h is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Algebraic factors in sieve files pepi37 Conjectures 'R Us 95 2017-07-04 13:37
option for finding multiple factors during trial factoring tha Software 24 2014-06-10 23:31
Constructing numbers that have S-smooth order CRGreathouse Math 7 2009-10-22 18:36
Trial Factoring Sieve? lfm Math 15 2009-04-07 11:20
program to verify factors found by sr(x)sieve? 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

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.