<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Jun 30, 2015 at 7:56 AM, Viktor Dukhovni <span dir="ltr"><<a href="mailto:cryptography@dukhovni.org" target="_blank">cryptography@dukhovni.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">> > So this approach is a dead-end even for the circle, which is much<br>
> > simpler than an actual Edwards curve with a non-zero "d"<br>
<br>
</span>That said, with a bit more thought (and a hint from Watson Ladd I<br>
should not have needed), there is a useful homomorphism if we're<br>
willing to abandon the rational circle for multiplication in a<br>
finite field.<br>
<br>
If p == 3 mod 4, choose $i^2 = -1$ in a quadratic extension $F_{p^2}$.<br>
If p == 1 mod 4, choose $i^2 = -1$ in the base field $F_p$.<br>
<br>
In either case the mapping (x,y) -> (x+iy) is an injective homomorphism<br>
(monic) from the circle group into the multiplication group of the<br>
corresponding finite field.  In fact for the 1 mod 4 case the<br>
mapping is an isomorphism.<br>
<br>
So DLP in the 1 mod 4 circle group is identical to DLP in F_p (plus<br>
the cost of finding a square root of p-1).<br>
<br>
DLP in the 3 mod 4 circle group is a sub-problem of DLP in F_{p^2},<br>
which is subject to essentially the same index calculus attacks as<br>
F_p, but now the smooth factor base uses gaussian integers.<br></blockquote><div><br></div><div>Thanks for this info.  That's very cool.</div><div><br></div><div>Given that the circle group seems roughy equivalent to regular DLP in difficulty, is it safe to say that finding a compactly representable point on the unit circle that maps to (x, y) mod p is equivalent in difficult to DLP?  This would explain why I am finding it difficult to do :-)</div><div><br></div><div>Bill</div></div></div></div>