20050414, 12:15  #1 
Apr 2005
3 Posts 
conversion to GF(2)
would it be possible to "convert"
GF(211921F4A73A3761B88323D6A34DF9E984D08FF25C491DF5DB3251310FAB9C36ACE903E01D41B9BF1EA5CBEAA79FD1D7036835E45933E34825B87C9AB45C2C4F^1) to GF(2), for utilizing Coppersmith's indexcalculus ? eg, convert from one GF representation to another, with all numbers converted to GF2, espeically the polynomial etc. Best Regards, Bud 
20050414, 13:45  #2  
"Bob Silverman"
Nov 2003
North of Boston
7464_{10} Posts 
Quote:
I will assume that the large hex number is prime. At least it is odd What do you mean by "convert"?? You are not changing representations within a fixed field; you are asking about some (hypothetical) relation between GF(p) and GF(2)??? You can conduct an index calculus attack on GF(p) by the number field sieve. The field given above would require a massive effort. Good luck. Can you clarify? 

20050414, 17:58  #3 
Apr 2005
3_{10} Posts 
Dear Dr Silverman,
Perhaps this is a stupid question, but the question is: Is it possible to convert modular arithmetices (espcially) discrete logs in prime fields GF(p) to GF(2) representation ? Like if we have an diskrete log like a^x mod p = b (which is to solve for x) in a prime field GF(p)  all parameters a,b,x,p elements of this field. Is there any possibility to convert those number to GF(2) like a,b elements in GF(2), p probably the irreducible polynomial, with the goal to solve the log in this field ? 
20050414, 18:18  #4 
May 2004
50_{16} Posts 
Is your question the following?
Does there exist a polynomialtime reduction from the problem "Discrete log in GF(p)" to the problem "Discrete log in GF(2^n)" ? I put the 2^n in there because I know of an *extremely* efficient algorithm to compute discrete logs in GF(2) Dave 
20050414, 18:35  #5 
Apr 2005
3 Posts 
Hello,
And thanks for the reply, the answer would indeed be yes, can we somehow translate our problem to GF(2) for usage of the powerful dlp solving algorithms which exists ? Are you talking about coppersmith's indexcalculus ? Best Regards 
20050414, 20:12  #6  
"Bob Silverman"
Nov 2003
North of Boston
1110100101000_{2} Posts 
Quote:
by "convert modular arithmetic in prime fields to GF(2) representation". What do you mean by "convert"? by "representation". All finite fields of a given order are isomorphic. Thus, any map from GF(a) to GF(b) will either be surjective or injective, depending on the size of the fields. There will never exist a 11 map unless the sizes are the same. The only time solving a discrete log in one field helps to solve a DL in another is if the first field is a subfield of the second AND the target log in the second field is in the orbit of the generator used in the first field. May I suggest that you do some reading about the structure of Finite Fields? Lidl & Neiderreiter's book is superb. NFS *IS* an index calculus algorithm. One can solve logs in GF(p) with it. 

20050414, 21:17  #7  
Apr 2004
Copenhagen, Denmark
116_{10} Posts 
Quote:
 Cheers, Jes 

20050414, 21:26  #8  
Feb 2005
FD_{16} Posts 
Quote:
Quote:


20050415, 12:23  #9  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:
One must solve the matrix mod p1, not just mod p. 

20050416, 01:13  #10  
Aug 2002
2^{6}×5 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Conversion GHz to GFLOPS?  preda  PrimeNet  11  20171202 21:51 
v5 Server Conversion  compusion  Software  3  20081114 19:22 
PS3 programmers(program conversion for pay?)  jasong  Programming  5  20071216 00:10 
Units Conversion Puzzle  JHagerson  Lounge  19  20051124 05:38 
Date conversion with Python  leifbk  Programming  2  20050126 23:00 