20071206, 14:42  #1 
"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 (<x) is 2kp+1 a multiple of x? Is there a clever way of answering(/programming) this? David Last fiddled with by davieddy on 20071206 at 15:14 
20071206, 14:51  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
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. 

20071206, 15:36  #3  
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Quote:
David 

20071206, 16:42  #4 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 

20071206, 18:27  #5 
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; } Last fiddled with by lavalamp on 20071206 at 18:37 
20071206, 18:30  #6 
Jun 2003
3^{4}·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) 
20071206, 19:05  #7  
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
Quote:
Is there anything simpler? Last fiddled with by davieddy on 20071206 at 19:08 

20071206, 19:11  #8 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 

20071206, 19:41  #9  
Feb 2007
2^{4}×3^{3} Posts 
Quote:
Note that if x is prime then Z/xZ is a field and thus there is only one kvalue 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\d1 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 xs 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 20071206 at 19:43 

20071206, 19:45  #10  
Oct 2007
Manchester, UK
1,373 Posts 
Oops, slight correction.
Quote:
Code:
flip k bit to (((res * k +1)%x == 0)?0:1); 

20071206, 20:06  #11 
Feb 2007
2^{4}×3^{3} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Algebraic factors in sieve files  pepi37  Conjectures 'R Us  95  20170704 13:37 
option for finding multiple factors during trial factoring  tha  Software  24  20140610 23:31 
Constructing numbers that have Ssmooth order  CRGreathouse  Math  7  20091022 18:36 
Trial Factoring Sieve?  lfm  Math  15  20090407 11:20 
program to verify factors found by sr(x)sieve?  mdettweiler  Software  16  20090308 02:06 