Prev: Protecting 3x16 bits with 16 bits ? (I wonder about LDPC codes for gpu ;))
Next: Security Proof of PACE
From: Mike Scott on 13 Feb 2010 07:09
http://www.scipub.org/fulltext/jcs/jcs59674-679.pdf
From: Mehdi Tibouchi on 13 Feb 2010 08:04
Mike Scott wrote in message <UGwdn.474$I8.450(a)news.indigo.ie>:
> http://www.scipub.org/fulltext/jcs/jcs59674-679.pdf

This is a rather trivial observation (namely that if you know the order,
or in this case the exponent, of (Z/nZ)^* for some RSA modulus n, you can
factor n), and the way it is presented here is misleading at best (it
claims to prove a relationship between DLP and factoring, but it's DLP in
(Z/nZ)^*, for which the claim is obvious, and not DLP over the
multiplicative group of finite fields, for which it would be a very
interesting breakthrough).
From: Pubkeybreaker on 15 Feb 2010 08:02
On Feb 13, 8:04 am, Mehdi Tibouchi <med...(a)alussinan.org> wrote:
> Mike Scott  wrote in message <UGwdn.474$I8....(a)news.indigo.ie>:
> >http://www.scipub.org/fulltext/jcs/jcs59674-679.pdf
>
> This is a rather trivial observation (namely that if you know the order,
> or in this case the exponent, of (Z/nZ)^* for some RSA modulus n, you can
> factor n), and the way it is presented here is misleading at best (it
> claims to prove a relationship between DLP and factoring, but it's DLP in
> (Z/nZ)^*, for which the claim is obvious, and not DLP over the
> multiplicative group of finite fields, for which it would be a very
> interesting breakthrough).

Indeed. It has been trivially known that integer factoring is P-TIME
equivalent
to finding a discrete log over a ring of unknown order for a long
time.

Note that the author does not present even a sub-exponential method
for
the latter. Instead, Pollard-Rho is suggested (a purely exponential
method)
 | 
Pages: 1
Prev: Protecting 3x16 bits with 16 bits ? (I wonder about LDPC codes for gpu ;))
Next: Security Proof of PACE