Cryptography Reference
In-Depth Information
import javax.swing.*;
public class TestSieveFactor {
public static void main(String[] args) {
boolean idiot;
do {
idiot=false;
try {
int n=new Integer(JOptionPane.showInputDialog
(“Enter an integer > 1:”)).intValue();
if (n<=1) {
idiot=true;
JOptionPane.showMessageDialog(null,”Invalid integer entered!”);
} else {
int d=sieveFactor(n);
if (d==n) JOptionPane.showMessageDialog(null,n+” is prime.”);
else JOptionPane.showMessageDialog(null,d+” divides “+n+”.”);
}
} catch (NumberFormatException e) {
idiot=true;
JOptionPane.showMessageDialog(null,e.toString());
}
} while (idiot);
System.exit(0);
}
private static int sieveFactor(int n) {
int divisor; boolean prime=true;
for (divisor=2;divisor<=Math.sqrt(n);divisor++)
if (n%divisor==0) {prime=false; break;}
return prime?n:divisor;
}
}
If we run the previous program with some test data, we get the results shown in Figure
3.1a-h.
The ability to factor efficiently is at the heart of breaking many cryptosystems. We thus
begin the study of finding divisors, or factors. In particular, we want to find the greatest
common divisor of two integers.
Definition
The greatest common divisor of two integers
and
, where at least one is nonzero, is
x
y
the largest integer that divides both
and
. We also call this the gcd of
and
, and write
x
y
x
y
it as (
,
). We define the greatest common divisor of 0 and 0 as 0; that is, (0, 0) = 0.
x
y
Search WWH ::
Custom Search