blade server on Sat, 20 Aug 2011 18:04:07 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Unable to run script


Hi, thanks for the feedback. Changes to the Keygen portion made.
Do highlight any other comments would be greatly appreciated.
Apologies if I had reply in a wrong way, not much experience in using a mailing list.

Regards

On Sat, Aug 20, 2011 at 11:06 PM, Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> wrote:
* blade server [2011-08-20 11:33]:
> Hi,
>
> Had a script that can't be run.
> Keep prompting syntax error, unexpected ')', expecting KPARROW or ',': ....
>
> Try to google for more inform on KPARROW but was not able to find things
> related to it.
>
> Thus would like to seek some advice on this list.

The first

 until((bitsize(p)>=x),

in Keygen() is missing a closing ')' somewhere.


A few random remarks

1) you should indent your scripts so that the structure becomes clearer, e.g.

 until((bitsize(p)>=x),
 p=lookprime(enlar);
 \\q=divisors(p-1)[1];
 test=1;
 until((isprime(q))&&(bitsize(q)>=y),
 if((test>numdiv(p-1)),
 break;
 );
 q=divisors(p-1)[test];
 test++;
 );

===>

 until((bitsize(p)>=x),
   p=lookprime(enlar);
   \\q=divisors(p-1)[1];
   test=1;
   until((isprime(q))&&(bitsize(q)>=y),
     if((test>numdiv(p-1)),
       break;
     );
     q=divisors(p-1)[test];
     test++;
   );

2) The numdiv(p-1) / divisors(p-1) are fixed and should be moved out of
the second 'until' loop. In fact, even then, this would be highly
inefficient. Use something like

 Q = factor(p-1)[,1]            \\ prime divisors of p-1
 if (bitsize(Q[#Q]) >= y, ...)  \\ largest prime divisor of p-1

3) It's immaterial here, but you probably want to start using my() rather than
local() [ see manual for the differences between the 2 ]

4) Sequences of print() statements quickly become unreadable; printf()
is your friend:

  print("P= ",p);print(" |p|_2= ",bitsize(p));

==>

  printf("P = %d, |p|_2 = %d", p, bitsize(p));

5) Sequences of boolean tests are evaluated from left to right:
expressions like

  (isprime(q))&&(bitsize(q)>=y)

are highly inefficient (contains 2 tests, the first one being slow, the
second one trivial). The following is much better:

 (bitsize(q)>=y) && (isprime(q))

6) No need to enclose tests within parentheses: it is enough to write

 bitsize(q)>=y && isprime(q)

7) Sequences of lift / Mod quickly become unreadable: decide once and for all
whether you want to use t_INTs or t_INTMODs (almost certainly the latter).
Once a sensible base ring is thus fixed, you can use lift() for printing
purposes (only). E.g.

 w=lift(1/Mod(s,q));
 u1=lift(Mod(m*w,q));
 u2=lift(Mod(r*w,q));
 v=lift(Mod(lift(Mod((g^u1)*(y1^u2),p)),q));

Since g / y1 are t_INTs, the last line is almost certainly not why you want
[ computing g^u1 requires exponential time in log(p) ! ] Compare:

 \\ ASSUME that g and y1 are t_INTMOD mod p, requires modifying Keygen()
 s = Mod(s, q) \\ paranoia in case s is a t_INT or t_INTMOD mod p*q
 w = 1 / s;
 u1 = lift(m*w); \\ t_INT exponent
 u2 = lift(r*w);
 v = Mod(g^u1 * y1^u2, q);

I have more comments, but please rewrite your script first.

Cheers,

   K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405
Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`

Attachment: dsa.gp
Description: Binary data