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

Yes, exactly 13, see for example http://www2.warwick.ac.uk/fac/cross_fac/complexity/people/students/dtc/students2013/klaise/janis_klaise_ug_report.pdf

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru
12 декабря 2015 г., 18:23, "Dan Brown" <dbrown@certicom.com> написал:
> 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