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