Please Help With a Module
- To: mathgroup at smc.vnet.net
- Subject: [mg40947] Please Help With a Module
- From: "flip" <flip_alpha at safebunch.com>
- Date: Fri, 25 Apr 2003 08:04:19 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Hello,
I was hoping I could get some help writing a module.
Algorithm:
1. Choose a random prime p.
2. Choose a PrimitiveRoot of and call it g
3. Choose a factor base set S = {Prime[1], Prime[2], ..., Prime[t]} (that
is, choose the first t primes)
4. Randomly choose k, where 1 <= k <= p-1 until PowerMod[g, k, p] has a
FactorInteger set which contains only some subset of the elements of S.
Example:
p = 229
g = 6 (assume I have a method of finding a g, but we can fix that for this
problem)
S = {2, 3, 5, 7, 11}
Now I'd like a module where I pass p and g, and it randomly chooses k's and
does the following (I gave many examples below as need to find many of
these, for example six such k's, which would be nice to select as a module
input also!)
FactorInteger[PowerMod[6, 100, 229]] = {{2, 2}, {3, 2}, {5, 1}} =
2^2*3^2*5^1 (each factor 2, 3, and 5 is in S so keep this one)
FactorInteger[PowerMod[6, 25, 229]] = {{73, 1}} = 73^1 (73 is not in S,
throw out)
FactorInteger[PowerMod[6, 18, 229]] = {{2, 4}, {11, 1}} = 2^4*11^1 (each
factor 2, 11 is in S so keep this one)
FactorInteger[PowerMod[6, 12, 229]] = {{3, 1}, {5, 1}, {11, 1}} =
3^1*5^1*11^1 (each factor 3, 5, 11 is in S so keep this one)
FactorInteger[PowerMod[6, 62, 229]] = {{2, 1}, {7, 1}, {11, 1}} =
2^1*7^1*11^1 (each factor 2, 7, 11 is in S so keep this one)
FactorInteger[PowerMod[6, 143, 229]] = {{2, 1}, {3, 2}, {11, 1}} (each
factor 2, 7, 11 is in S so keep this one)
FactorInteger[PowerMod[6, 109, 229]] = {{23, 1}} (23 is not in S so throw
out)
FactorInteger[PowerMod[6, 135, 229]] = {{227, 1}} (227 is not in S so throw
out)
FactorInteger[PowerMod[6, 145, 229]] = {{29, 1}} (29 is not in S so throw
out)
FactorInteger[PowerMod[6, 206, 229]] = {{2, 1}, {3, 1}, {5, 1}, {7, 1}}
(each factor 2, 7, 11 is in S so keep this one)
(* Even a modulw that just does the above would be great! *)
So, we found the six good elements (above) and can put them in matrix form
(the length of the row is the length of S):
So, for 2^2*3^2*5^1 (the first good item above, we get) - notice that we
have elements from S in position 2, 3, and 5, but not 7 and 11!
2a + 2b +1c + 0d + 0e == 100 (note, we only take the powers and positions of
S where the factor occurs, and 100 was the the random k)
The next good output above s 2^4 *11^1, so we get - notice we only have
elements from S in position 2 and 11, not 3, 5, and 7!
4a + 0b + 0c + 0d + 1e == 18
Continuing in this fashion, we end up with:
Solve[{
2a + 2b + 1c + 0d + 0e == 100,
4a + 0b + 0c + 0d + 1e == 18,
0a + 1b + 1b + 0d + 1e == 12,
1a + 0b + 0c + 0d + 1e == 62,
1a + 2b + 0c + 0d + 1e == 143,
1a + 1b + 1c + 1d + 0e == 206,
Modulus == p-1}]
and get a = 21, b = 208, c = 98, d = 107, e = 162.
Can someone help here (doing these steps manually is brutal!!!)?
Thank you for any help!
Flip
To email me, remove "_alpha".
- Follow-Ups:
- Re: Please Help With a Module
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: Please Help With a Module