| Frames | No Frames |
1: /* Prime.java --- Prime number generation utilities 2: Copyright (C) 1999, 2004 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package gnu.java.security.util; 40: import java.math.BigInteger; 41: import java.util.Random; 42: //import java.security.SecureRandom; 43: 44: public final class Prime 45: { 46: 47: /* 48: See IEEE P1363 A.15.4 (10/05/98 Draft) 49: */ 50: public static BigInteger generateRandomPrime( int pmin, int pmax, BigInteger f ) 51: { 52: BigInteger d; 53: 54: //Step 1 - generate prime 55: BigInteger p = new BigInteger( (pmax + pmin)/2, new Random() ); 56: if( p.compareTo( BigInteger.valueOf( 1 ).shiftLeft( pmin ) ) <= 0 ) 57: { 58: p = p.add( BigInteger.valueOf( 1 ).shiftLeft( pmin ).subtract( p ) ); 59: } 60: 61: //Step 2 - test for even 62: if( p.mod( BigInteger.valueOf(2) ).compareTo( BigInteger.valueOf( 0 )) == 0) 63: p = p.add( BigInteger.valueOf( 1 ) ); 64: 65: for(;;) 66: { 67: //Step 3 68: if( p.compareTo( BigInteger.valueOf( 1 ).shiftLeft( pmax)) > 0) 69: { 70: //Step 3.1 71: p = p.subtract( BigInteger.valueOf( 1 ).shiftLeft( pmax) ); 72: p = p.add( BigInteger.valueOf( 1 ).shiftLeft( pmin) ); 73: p = p.subtract( BigInteger.valueOf( 1 ) ); 74: 75: //Step 3.2 76: // put step 2 code here so looping code is cleaner 77: //Step 2 - test for even 78: if( p.mod( BigInteger.valueOf(2) ).compareTo( BigInteger.valueOf( 0 )) == 0) 79: p = p.add( BigInteger.valueOf( 1 ) ); 80: continue; 81: } 82: 83: //Step 4 - compute GCD 84: d = p.subtract( BigInteger.valueOf(1) ); 85: d = d.gcd( f ); 86: 87: //Step 5 - test d 88: if( d.compareTo( BigInteger.valueOf( 1 ) ) == 0) 89: { 90: //Step 5.1 - test primality 91: if( p.isProbablePrime( 1 ) == true ) 92: { 93: //Step 5.2; 94: return p; 95: } 96: } 97: //Step 6 98: p = p.add( BigInteger.valueOf( 2 ) ); 99: 100: //Step 7 101: } 102: } 103: 104: 105: /* 106: See IEEE P1363 A.15.5 (10/05/98 Draft) 107: */ 108: public static BigInteger generateRandomPrime( BigInteger r, BigInteger a, int pmin, int pmax, BigInteger f ) 109: { 110: BigInteger d, w; 111: 112: //Step 1 - generate prime 113: BigInteger p = new BigInteger( (pmax + pmin)/2, new Random() ); 114: 115: steptwo:{ //Step 2 116: w = p.mod( r.multiply( BigInteger.valueOf(2) )); 117: 118: //Step 3 119: p = p.add( r.multiply( BigInteger.valueOf(2) ) ); 120: p = p.subtract( w ); 121: p = p.add(a); 122: 123: //Step 4 - test for even 124: if( p.mod( BigInteger.valueOf(2) ).compareTo( BigInteger.valueOf( 0 )) == 0) 125: p = p.add( r ); 126: 127: for(;;) 128: { 129: //Step 5 130: if( p.compareTo( BigInteger.valueOf( 1 ).shiftLeft( pmax)) > 0) 131: { 132: //Step 5.1 133: p = p.subtract( BigInteger.valueOf( 1 ).shiftLeft( pmax) ); 134: p = p.add( BigInteger.valueOf( 1 ).shiftLeft( pmin) ); 135: p = p.subtract( BigInteger.valueOf( 1 ) ); 136: 137: //Step 5.2 - goto to Step 2 138: break steptwo; 139: } 140: 141: //Step 6 142: d = p.subtract( BigInteger.valueOf(1) ); 143: d = d.gcd( f ); 144: 145: //Step 7 - test d 146: if( d.compareTo( BigInteger.valueOf( 1 ) ) == 0) 147: { 148: //Step 7.1 - test primality 149: if( p.isProbablePrime( 1 ) == true ) 150: { 151: //Step 7.2; 152: return p; 153: } 154: } 155: //Step 8 156: p = p.add( r.multiply( BigInteger.valueOf(2) ) ); 157: 158: //Step 9 159: } 160: } 161: //Should never reach here but makes the compiler happy 162: return BigInteger.valueOf(0); 163: } 164: }