Constructing numbers that have S-smooth order

CRGreathouse · 2009-10-21, 18:55

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?

R.D. Silverman · 2009-10-21, 19:53

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?

CRGreathouse · 2009-10-21, 20:34

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.

R. Gerbicz · 2009-10-21, 20:44

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.

CRGreathouse · 2009-10-21, 20:54

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?

R. Gerbicz · 2009-10-21, 21:14

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)).

CRGreathouse · 2009-10-21, 23:16

Oh got it. I hadn't thought of using that for some reason...

Hmm. Time to write a quick siever.

CRGreathouse · 2009-10-22, 18:36

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).

2009-10-21, 18:55	#1
CRGreathouse Aug 2006 5,987 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, 20:44	#4
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 5×17×19 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*

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

2009-10-21, 23:16	#7
CRGreathouse Aug 2006 5987₁₀ 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 5,987 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).