mersenneforum.org > Math Constructing numbers that have S-smooth order
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-21, 18:55 #1 CRGreathouse     Aug 2006 32×5×7×19 Posts Constructing numbers that have S-smooth order I have a small finite set S = {5, 311, ...} (with, say, less than 30 elements; most are large) and I'm trying to find all primes p in [1..N] such that the order of 6 mod p is S-smooth. By S-smooth, I mean numbers n such that p|n --> p in S for all primes p. By order of n mod p, I mean the least positive k such that n^k = 1 (mod p). Is there a good way to do this? I have been able to search up to N = 10^9 directly, but this is time-consuming. For most primes, 6 has an order mod p that is divisible by 2, 3, 7, 11, 13, ..., 307, 313, ... and it seems that there should be a good way to exclude these. Is there an efficient way to go from S-smooth numbers below N to the primes with those orders?
2009-10-21, 19:53   #2
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by CRGreathouse I have a small finite set S = {5, 311, ...} (with, say, less than 30 elements; most are large) and I'm trying to find all primes p in [1..N] such that the order of 6 mod p is S-smooth. By S-smooth, I mean numbers n such that p|n --> p in S for all primes p. By order of n mod p, I mean the least positive k such that n^k = 1 (mod p). Is there a good way to do this? I have been able to search up to N = 10^9 directly, but this is time-consuming. For most primes, 6 has an order mod p that is divisible by 2, 3, 7, 11, 13, ..., 307, 313, ... and it seems that there should be a good way to exclude these. Is there an efficient way to go from S-smooth numbers below N to the primes with those orders?
#S ~ 30, so there are 2^30 subsets. Construct them. For each
subset multiply the elements and add 1. Eliminate the composites from
this resulting set of integers.

This leaves a set of primes for which ALL integers, not just 6 will have
smooth order. Why is 6 special?

2009-10-21, 20:34   #3
CRGreathouse

Aug 2006

32×5×7×19 Posts

I actually need all of the primes below N with ord(6, p) S-smooth, not just some. Constructing all the 2^30 squarefrees would miss 155501, which has order 5^3 * 311.

Also, I have a new set S' with 50 elements.

I can construct the S-smooth numbers with an iterative process, and I think this would be reasonably efficient. But the associated primes can be sk + 1 for some k, not just s + 1, for s S-smooth.

Quote:
 Originally Posted by R.D. Silverman Why is 6 special?
That just happens to be the problem I'm working on -- I mentioned it only in case it would allow further optimizations.

 2009-10-21, 20:44 #4 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 101101110102 Posts How large is N? If it is small then it is possible to compute all primes up to N and their order's mod 6 by sieve in O(N*(log(N)^c)) time. Last fiddled with by R. Gerbicz on 2009-10-21 at 20:45
2009-10-21, 20:54   #5
CRGreathouse

Aug 2006

10111011000012 Posts

Quote:
 Originally Posted by R. Gerbicz How large is N? If it is small then it is possible to compute all primes up to N and their order's mod 6 by sieve in O(N*(log(N)^c)) time.
I've computed it for N = 10^9, but I'd like to go to 10^12 or 10^15.

Not to be dumb, but what's the algorithm?

2009-10-21, 21:14   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·733 Posts

Quote:
 Originally Posted by CRGreathouse I've computed it for N = 10^9, but I'd like to go to 10^12 or 10^15. Not to be dumb, but what's the algorithm?
Here it is a small code in Pari for that:

Code:
ord(a,p)=u=factor(p-1);w=matsize(u);T=1;for(i=1,w[1],q=u[i,1];e=u[i,2];\
b=Mod(a,p)^((p-1)/q^e);while(b!=Mod(1,p),T*=q;b=b^q));return(T)
Obviously it is much better to replace the factorization of (p-1) by sieving.

You can check my code by Pari calling znorder(Mod(a,p)).

Last fiddled with by R. Gerbicz on 2009-10-21 at 21:17

 2009-10-21, 23:16 #7 CRGreathouse     Aug 2006 32·5·7·19 Posts Oh got it. I hadn't thought of using that for some reason... Hmm. Time to write a quick siever.
 2009-10-22, 18:36 #8 CRGreathouse     Aug 2006 10111011000012 Posts Wait, I think I have a faster way. Make an array that fits into memory representing the numbers from N/2 to N/2+step; initialize to 1. For each element p in S, set arr[n] to arr[n] * p if p^k | 2n (of course this is the same as p^k | n in my case) for k = 1, ..., log_p (N+2step) by sieving. Then for each odd prime p less than some reasonable bound, set arr[n] to 1 if p | 2n+1. Step through the array, looking for n with arr[n] > 1. For such n, calculate 6^arr[n] (mod 2n+1). If it is equal to 1, output 2n+1; its order divides arr[n] and hence is S-smooth. This way there's much less sieving and less work needed for calculating the order. If the second bound is less than sqrt(N+2step) some nonprimes will be tested, but that's OK. (Very few numbers will be output, and those can be tested with a usual primality testing algorithm if desired).

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Sam Kennedy Factoring 5 2012-11-10 07:54 Citrix Other Mathematical Topics 46 2012-03-06 14:55 CRGreathouse Math 3 2009-05-25 05:26 Citrix Math 9 2005-12-31 11:07 Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 17:31.

Sun May 9 17:31:28 UTC 2021 up 31 days, 12:12, 1 user, load averages: 4.92, 4.41, 4.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.