20091021, 18:55  #1 
Aug 2006
3^{2}×5×7×19 Posts 
Constructing numbers that have Ssmooth 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 Ssmooth.
By Ssmooth, I mean numbers n such that pn > 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 timeconsuming. 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 Ssmooth numbers below N to the primes with those orders? 
20091021, 19:53  #2  
Nov 2003
16444_{8} Posts 
Quote:
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? 

20091021, 20:34  #3 
Aug 2006
3^{2}×5×7×19 Posts 
I actually need all of the primes below N with ord(6, p) Ssmooth, 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 Ssmooth 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 Ssmooth. That just happens to be the problem I'm working on  I mentioned it only in case it would allow further optimizations. 
20091021, 20:44  #4 
"Robert Gerbicz"
Oct 2005
Hungary
10110111010_{2} 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 20091021 at 20:45 
20091021, 20:54  #5 
Aug 2006
1011101100001_{2} Posts 

20091021, 21:14  #6  
"Robert Gerbicz"
Oct 2005
Hungary
2·733 Posts 
Quote:
Code:
ord(a,p)=u=factor(p1);w=matsize(u);T=1;for(i=1,w[1],q=u[i,1];e=u[i,2];\ b=Mod(a,p)^((p1)/q^e);while(b!=Mod(1,p),T*=q;b=b^q));return(T) You can check my code by Pari calling znorder(Mod(a,p)). Last fiddled with by R. Gerbicz on 20091021 at 21:17 

20091021, 23:16  #7 
Aug 2006
3^{2}·5·7·19 Posts 
Oh got it. I hadn't thought of using that for some reason...
Hmm. Time to write a quick siever. 
20091022, 18:36  #8 
Aug 2006
1011101100001_{2} 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 Ssmooth. 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 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Special Smooth numbers  Citrix  Other Mathematical Topics  46  20120306 14:55 
Smooth and rough numbers  CRGreathouse  Math  3  20090525 05:26 
Finding smooth numbers  Citrix  Math  9  20051231 11:07 
Smooth Numbers  Yamato  Math  1  20051211 11:09 