CARAMEL Curve Cardinality Computation C Coding Contest

This contest was first presented at the Rump session of ANTS-IX in Nancy. Check out the slides for more information.

Genus-1 point counting

• Shortest code: Antoine Joux (105 bytes)
  Usage: echo p a b | ./a.out (for 2 < p ≤ 1289)
  

  p,a,b,X,Y;main(C){for(scanf("%d%d%d",&p,&a,&b);(X=Y++
  /p)<p;)(X*X*X+a*X+b-Y%p*Y)%p?:C++;printf("%d\n",C);}
  

• Artistic mention: Mehdi Tibouchi (205 bytes)
  Usage: echo a b p | ./a.out (for 2 < p ≤ 46337)
  

  a[3],r,x,u,v,s,t=3;main(){for(;t--;scanf("%d",a+t));for(;x++<*a||!printf
  ("%d\n",1+r+*a);r+=s*v)for(v=*a,s=1,u=(x*x+a[2])%v*x+s[a];v>1;u^=v^=u^=v
  ,s=(u&v^t+t&(u/2^u))&2?-s:s)for(u%=v,t=0;u&&!(u&1);u/=2)t++;}
  

Genus-2 point counting

• CARAMEL logo: (255 bytes)
  Usage: echo f₃ f₂ f₁ f₀ p | ./a.out (for 2 < p ≤ 997)
  

               /*   CARAMEL project-team    */                  C,A,
               /*  Cryptology, Arithmetic:  */                 R,a,
               /*   Hardware and Software   */                M,E,
                                                             L,i=
                                                            5,e,
      d[5],Q[999                  ]={0};main(N            ){for
    (;i--;e=scanf("%"           "d",d+i));for(A           =*d;
   ++i<A         ;++Q[         i*i%          A],R=       i[Q]?
  R:i);            for(;i     --;)            for(M      =A;M
  --;N             +=!M*Q     [E%A            ],e+=      Q[(A
  +E*E-           R*L*         L%A)           %A])        for(
    E=i,L=M,a=4;a;C=            i*E+R*M*L,L=(M*E          +i*L)
      %A,E=C%A+a                 --[d]);printf             ("%d"
                                                            "\n",
                                                             (e+N*
                                                               N)/2
       /* cc caramel.c; echo f3 f2 f1 f0 p | ./a.out */        -A);}
  

• Shortest code: CARAMEL (255 bytes), Thorsten Kleinjung (253) and Emmanuel Thomé (249)
  Usage: echo f₃ f₂ f₁ f₀ p | ./a.out (for 2 < p ≤ 997)
  

  H,p,X=5,J,D,i,Y,Z,T,f[5],Q[999];main(C){for(;X--;J=scanf("%d",
  f+X));for(p=*f;++X<p;Q[X*X%p]++)D=X[Q]?D:X;for(;X--;)for(Y=p;Y
  ;C+=!Y*Q[Z%p],J+=Q[(p+Z*Z-D*T*T%p)%p])for(Z=X,T=--Y,i=4;i;T=(Y
  *Z+X*T)%p,Z=H%p+i--[f])H=X*Z+D*Y*T;printf("%d\n",(J+C*C)/2-p);}
  

How to participate?