Re: Please Help With a Module
- To: mathgroup at smc.vnet.net
- Subject: [mg40973] Re: [mg40947] Please Help With a Module
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sat, 26 Apr 2003 03:25:16 -0400 (EDT)
- References: <200304251204.IAA09606@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
flip wrote:
>
> 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".
It looks like you want to compute discrete logs base-g of elements in
your factor base?
I don't have time to work on explicit code but I will make a comment
that may matter for efficiency should you wish to do this with
significantly larger p. The issue is that those FactorInteger uses may
become slow. But the potentially slow ones can be avoided.
For each element q[j] in your factor base, let e[j] be the floor of the
log of p base q[j]. Form the product qe = q[j]^e[j] (j iterates over
your factor base). In your example, for instance, we would have
In[17]:= factorbase = Prime[Range[5]]
Out[17]= {2, 3, 5, 7, 11}
In[18]:= expons = Floor[Log[factorbase,229]]
Out[18]= {7, 4, 3, 2, 2}
In[19]:= qe = Apply[Times, factorbase^expons]
Out[19]= 7683984000
Then your PowerMod result, pm, will split into factors involving only
the factor base if and only if the GCD of pm and qe is pm itself. Only
in such cases need you employ FactorInteger, and it will be fast for
those cases because it will require only trial division to fully factor
pm.
Daniel Lichtblau
Wolfram Research
- References:
- Please Help With a Module
- From: "flip" <flip_alpha@safebunch.com>
- Please Help With a Module