Re: [Cfrg] Question about A=6 Montgomery over 2^89-1

So 66^3 is one of the few (13???) integral j-invariants with CM over the rationals (the Baker-Stark-Heegner theorem?). And yes Elkies shows that half the primes will give a supersingular. I'll look at how j=66^3 corresponds to A=6 in 2016, and eventually try to sort out whether there's much to say about small |A|.

  Original Message
From: Grigory Marshalko
Sent: Friday, December 11, 2015 4:09 PM
To: Dan Brown; cfrg@ietf.org
Subject: Re: [MASSMAIL][Cfrg] Question about A=6 Montgomery over 2^89-1

This seems to be a better answer

http://alexricemath.com/wp-content/uploads/2013/07/EC2.pdf

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru
11 декабря 2015 г., 23:20, "Grigory Marshalko" <marshalko_gb@tc26.ru> написал:

> Hi,
>
> May be this is the case:
> from wiki:
> If an elliptic curve over the rationals has complex multiplication then the set of primes for which
> it is supersingular has density 1/2. If it does not have complex multiplication then Serre showed
> that the set of primes for which it is supersingular has density zero. Elkies (1987) showed that
> any elliptic curve defined over the rationals is supersingular for an infinite number of primes.
>
> and this is also may be useful http://pages.cs.wisc.edu/~cdx/ComplexMult.pdf
>
> Regards,
> Grigory Marshalko,
> expert,
> Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
> www.tc26.ru
> 11 декабря 2015 г., 00:22, "Dan Brown" <dbrown@certicom.com> написал:
>
>> Hi,
>>
>> I stumbled upon something surprising (to me), using Sage (while searching
>> for something else).
>>
>> The Montgomery curve y^2 = x^3 + 6x^2 + x over the field of size 2^89-1, has
>> order 2^89, so it is maximally vulnerable to Pohlig-Hellman. (Other
>> details: it has order p+1, so is also vulnerable to MOV. I haven't checked
>> yet, but I'd _bet_ it's supersingular. It has j-invariant 66^3.)
>>
>> As is well-known, the supersingular curve y^2 = x^3 + x also has order 2^89
>> (it has j-invariant 1728=12^3). But I recall a result of Koblitz saying
>> that curves over F_p with order p+1 are very rare (among isomorphism
>> classes). Naively, I would think that finding two such curves so close
>> together (A=0 and A= 6) has negligible chance, unless these weak curves are
>> distributed towards small |A|.
>>
>> Nonetheless, I still hope that this does _not_ indicate some general _weak_
>> correlation between Montgomery curves with a small coefficient and known
>> attacks.
>>
>> To that end, I'd be curious if somebody here could explain the theory behind
>> this example curve. For example, it would be re-assuring to explain this as
>> a mere one-time coincidence, rather than a higher chance of a known attack
>> (e.g. MOV or PH) on smaller-coefficient curves. (Purely speculating: maybe
>> there's a good theory of supersingular j-invariants for each prime p, then a
>> way to deduce A from j, such that p=2^89-1 and j=66^3 formed a superstorm to
>> arrive at a small A=6.)
>>
>> Absent such an explanation, the worry is that if known attacks more
>> generally exhibit this kind of correlation with coefficient size, then how
>> wise is it to suggest small-coefficient curve as a remedy against secret
>> attacks?
>>
>> I am aware that there are other worries of a different nature
>> ("manipulation") involved with methods that generate larger coefficients,
>> but maybe there's a good way to balance both concerns.
>>
>> Best regards,
>>
>> Daniel Brown
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg