I am no cryptographer, so please take my comments for what they are
worth. I am also not sure what Tom's specific concern is.
The use of the looping construct is ugly. However, it seems to me to
faithfully implement the algorithm described. I believe the algorithm
could be refactored so that it would not result in such ugly code,
but I am not sure of the wisdom of that. There seems to be merit in
sticking closely to a published and readily available algorithm.
I fail to see why the while loop was put in though. It does not alter
the behavior of the code (if I understand 'continue steptwo', that
is) and, in my opinion, it does not make the code any less ugly, on
the contrary.
I am surprised that the pmin and pmax parameters are interpreted as
only conveying information about the desired bitlength of the result.
I don't think that is the intention of the original algorithm. It
also seems to offer strange guarantees: the result will not be
greater than 2^n - 1 where n is the number of bits in pmax. Surely it
would be more intuitive either to guarantee
- that the result is no greater than pmax
- or that the result is no greater than 2^pmax - 1.
If the latter path were chosen, I assume that pmax could be an int (or perhaps a long).
Similar considerations obviously apply to pmin.
The guarantee that the result is prime seems rather weak considering
that isProbablePrime() is called with argument 1. Assuming that the
likelihood that steps 1 to 6 comes up with a prime is about 1/2, it
seems to me that isProbablePrime() should be called with argument 100
if the guarantee that the result of the function is prime should be
the same as that of BigInteger.probablePrime(), i.e. 1 - 2^(-100). As
it is, if isProbablePrime()'s implementation's guarantee is no
stronger than documented in Javadoc and, again, assuming that steps 1
to 6 generate a prime in 1 out of 2 cases, I think that
generateRandomPrime() yields a prime in 2 out of 3 cases. Has anyone
tested this?
I have a hunch that, unfortunately, the assumption that steps 1 to 6
generate a prime 1 in 2 cases is overoptimistic. If so, the
guarantees of the current implementation are even weaker and the
argument to isProbablePrime() would need to be increased further to
make them reasonable.
kr,
Yo
On 3 Mar 2004 at 12:03, Tom Tromey wrote:
> While debugging gcjx, I ran across some strange code in Prime.java.
> I think the intention was for the code to resemble the result of the
> appended patch. The patch looks big, but it just wraps the body in
a
> `while (true)' and changes a `break' to `continue'.
>
> Any comments on this? I didn't look up the IEEE spec that this
> references, for all I know the comments are the only part that are
> wrong.
>
> Tom
>
> Index: ChangeLog
> from Tom Tromey <[EMAIL PROTECTED]>
>
> * gnu/java/security/util/Prime.java (generateRandomPrime): Loop
> as intended.
>
> Index: gnu/java/security/util/Prime.java
> ===================================================================
> RCS file: /cvs/gcc/gcc/libjava/gnu/java/security/util/Prime.java,v
> retrieving revision 1.3
> diff -u -r1.3 Prime.java
> --- gnu/java/security/util/Prime.java 11 Aug 2002 16:34:44 -0000
1.3
> +++ gnu/java/security/util/Prime.java 3 Mar 2004 19:12:40 -0000
> @@ -1,5 +1,5 @@
> /* Prime.java --- Prime number generation utilities
> - Copyright (C) 1999 Free Software Foundation, Inc.
> + Copyright (C) 1999, 2004 Free Software Foundation, Inc.
>
> This file is part of GNU Classpath.
>
> @@ -105,60 +105,64 @@
> /*
> See IEEE P1363 A.15.5 (10/05/98 Draft)
> */
> - public static BigInteger generateRandomPrime( BigInteger r,
BigInteger a, int pmin, int pmax, BigInteger f )
> + public static BigInteger generateRandomPrime( BigInteger r,
BigInteger a,
> + int pmin, int pmax,
> + BigInteger f )
> {
> BigInteger d, w;
>
> //Step 1 - generate prime
> BigInteger p = new BigInteger( (pmax + pmin)/2, new Random()
);
>
> - steptwo:{ //Step 2
> - w = p.mod( r.multiply( BigInteger.valueOf(2) ));
> + steptwo:
> + while (true)
> + {
> + //Step 2
> + w = p.mod( r.multiply( BigInteger.valueOf(2) ));
> +
> + //Step 3
> + p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> + p = p.subtract( w );
> + p = p.add(a);
> +
> + //Step 4 - test for even
> + if( p.mod( BigInteger.valueOf(2) ).compareTo( BigInteger.valueOf(
0 ))
> + == 0)
> + p.add( r );
> +
> + for(;;)
> + {
> + //Step 5
> + if( p.compareTo( BigInteger.valueOf( 1 ).shiftLeft( pmax)) >
0)
> + {
> + //Step 5.1
> + p = p.subtract( BigInteger.valueOf( 1 ).shiftLeft( pmax) );
> + p = p.add( BigInteger.valueOf( 1 ).shiftLeft( pmin) );
> + p = p.subtract( BigInteger.valueOf( 1 ) );
> +
> + //Step 5.2 - goto to Step 2
> + continue steptwo;
> + }
> +
> + //Step 6
> + d = p.subtract( BigInteger.valueOf(1) );
> + d = d.gcd( f );
>
> - //Step 3
> - p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> - p = p.subtract( w );
> - p = p.add(a);
> -
> - //Step 4 - test for even
> - if( p.mod( BigInteger.valueOf(2) ).compareTo(
BigInteger.valueOf( 0 )) == 0)
> - p.add( r );
> -
> - for(;;)
> - {
> - //Step 5
> - if( p.compareTo( BigInteger.valueOf( 1 ).shiftLeft( pmax)) > 0)
> - {
> - //Step 5.1
> - p = p.subtract( BigInteger.valueOf( 1 ).shiftLeft( pmax) );
> - p = p.add( BigInteger.valueOf( 1 ).shiftLeft( pmin) );
> - p = p.subtract( BigInteger.valueOf( 1 ) );
> -
> - //Step 5.2 - goto to Step 2
> - break steptwo;
> - }
> -
> - //Step 6
> - d = p.subtract( BigInteger.valueOf(1) );
> - d = d.gcd( f );
> -
> - //Step 7 - test d
> - if( d.compareTo( BigInteger.valueOf( 1 ) ) == 0)
> - {
> - //Step 7.1 - test primality
> - if( p.isProbablePrime( 1 ) == true )
> - {
> - //Step 7.2;
> - return p;
> - }
> - }
> - //Step 8
> - p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> -
> - //Step 9
> - }
> - }
> - //Should never reach here but makes the compiler happy
> - return BigInteger.valueOf(0);
> + //Step 7 - test d
> + if( d.compareTo( BigInteger.valueOf( 1 ) ) == 0)
> + {
> + //Step 7.1 - test primality
> + if( p.isProbablePrime( 1 ) == true )
> + {
> + //Step 7.2;
> + return p;
> + }
> + }
> + //Step 8
> + p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> +
> + //Step 9
> + }
> + }
> }
> }
>
>
> _______________________________________________
> Classpath mailing list
> [EMAIL PROTECTED]
> http://mail.gnu.org/mailman/listinfo/classpath
>
--
Johan Peeters bvba
software architecture services
tel:+32 16 64900
http://www.johanpeeters.com
_______________________________________________
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
