mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-10-21, 18:55   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default 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?
CRGreathouse is offline   Reply With Quote
Old 2009-10-21, 19:53   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2009-10-21, 20:34   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2009-10-21, 20:44   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101110102 Posts
Default

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
R. Gerbicz is offline   Reply With Quote
Old 2009-10-21, 20:54   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000012 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2009-10-21, 21:14   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·733 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2009-10-21, 23:16   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

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

Hmm. Time to write a quick siever.
CRGreathouse is offline   Reply With Quote
Old 2009-10-22, 18:36   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000012 Posts
Cool

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).
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

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.