mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-04-14, 12:15   #1
bigbud
 
Apr 2005

3 Posts
Default conversion to GF(2)

would it be possible to "convert"

GF(211921F4A73A3761B88323D6A34DF9E984D08FF25C491DF5DB3251310FAB9C36ACE903E01D41B9BF1EA5CBEAA79FD1D7036835E45933E34825B87C9AB45C2C4F^1)

to GF(2), for utilizing Coppersmith's index-calculus ?

eg, convert from one GF representation to another, with all numbers converted to GF2, espeically the polynomial etc.

Best Regards, Bud
bigbud is offline   Reply With Quote
Old 2005-04-14, 13:45   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Thumbs up

Quote:
Originally Posted by bigbud
would it be possible to "convert"

GF(211921F4A73A3761B88323D6A34DF9E984D08FF25C491DF5DB3251310FAB9C36ACE903E01D41B9BF1EA5CBEAA79FD1D7036835E45933E34825B87C9AB45C2C4F^1)

to GF(2), for utilizing Coppersmith's index-calculus ?

eg, convert from one GF representation to another, with all numbers converted to GF2, espeically the polynomial etc.

Best Regards, Bud

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?
R.D. Silverman is offline   Reply With Quote
Old 2005-04-14, 17:58   #3
bigbud
 
Apr 2005

3 Posts
Default

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 ?
bigbud is offline   Reply With Quote
Old 2005-04-14, 18:18   #4
dave_dm
 
May 2004

24×5 Posts
Default

Is your question the following?

Does there exist a polynomial-time 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
dave_dm is offline   Reply With Quote
Old 2005-04-14, 18:35   #5
bigbud
 
Apr 2005

3 Posts
Default

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 index-calculus ?

Best Regards
bigbud is offline   Reply With Quote
Old 2005-04-14, 20:12   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Thumbs up

Quote:
Originally Posted by bigbud
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 ?
The question isn't "stupid" per se, but I don't understand what you mean
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 1-1 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 sub-field 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.
R.D. Silverman is offline   Reply With Quote
Old 2005-04-14, 21:17   #7
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

7416 Posts
Default

Quote:
Originally Posted by R.D. Silverman
NFS *IS* an index calculus algorithm. One can solve logs in GF(p) with it.
I've never seen an implementation of NFS for discrete logs. Do you know anybody who has made an efficient implementation? If so, how large can p be, if you want to be able to solve a discrete log in GF(p) in 1GHz month, say?

--
Cheers,
Jes
JHansen is offline   Reply With Quote
Old 2005-04-14, 21:26   #8
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by JHansen
I've never seen an implementation of NFS for discrete logs. Do you know anybody who has made an efficient implementation?
Look at http://www.cs.toronto.edu/~cvs/dlog/
Quote:
Originally Posted by JHansen
If so, how large can p be, if you want to be able to solve a discrete log in GF(p) in 1GHz month, say?
If you measured that I'd be interested in knowing the answer.
maxal is offline   Reply With Quote
Old 2005-04-15, 12:23   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Thumbs up

Quote:
Originally Posted by JHansen
I've never seen an implementation of NFS for discrete logs. Do you know anybody who has made an efficient implementation? If so, how large can p be, if you want to be able to solve a discrete log in GF(p) in 1GHz month, say?

--
Cheers,
Jes
O. Schirakauer has an implementation, AFAIK. The big headache is the LA.
One must solve the matrix mod p-1, not just mod p.
R.D. Silverman is offline   Reply With Quote
Old 2005-04-16, 01:13   #10
ColdFury
 
ColdFury's Avatar
 
Aug 2002

1010000002 Posts
Default

Quote:
Originally Posted by R.D. Silverman
O. Schirakauer has an implementation, AFAIK. The big headache is the LA.
One must solve the matrix mod p-1, not just mod p.
Indeed, this is where my toy implementation failed.
ColdFury is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Conversion GHz to GFLOPS? preda PrimeNet 11 2017-12-02 21:51
v5 Server Conversion compusion Software 3 2008-11-14 19:22
PS3 programmers(program conversion for pay?) jasong Programming 5 2007-12-16 00:10
Units Conversion Puzzle JHagerson Lounge 19 2005-11-24 05:38
Date conversion with Python leifbk Programming 2 2005-01-26 23:00

All times are UTC. The time now is 14:28.

Sun Oct 25 14:28:39 UTC 2020 up 45 days, 11:39, 1 user, load averages: 1.90, 1.60, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.