/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/bases/PowMod.java |
---|
0,0 → 1,38 |
package de.viathinksoft.immortal.bases; |
/** |
* Powmod.java |
* |
* Implementation von a^b mod m durch iteriertes Quadrieren. Zum Testen: Der |
* Aufruf java powmod a b m gibt a^b mod m aus. |
* |
* @author Thorsten Altenkirch |
* @version Modified by Daniel Marschall |
* |
*/ |
public class PowMod { |
/** |
* Ermittelt das nte Bit von l |
*/ |
private static boolean bit(long l, int n) { |
return (((l >> n) & 1) != 0); |
} |
/** |
* Berechnet a^b mod m durch iteriertes Quadrieren. |
*/ |
public static long powmod(long a, long m, long n) { |
long y = 1; |
for (int i = 62; i >= 0; i--) { |
y = y * y % n; |
if (bit(m, i)) { |
y = a * y % n; |
} |
} |
return y; |
} |
private PowMod() { |
} |
} |
/ViaThinkSoft Distributed/src/de/viathinksoft/immortal/bases/SearchRoots.java |
---|
0,0 → 1,31 |
package de.viathinksoft.immortal.bases; |
import java.util.Vector; |
public class SearchRoots { |
public static boolean isImmortal(int num, int base) { |
String quadrat = "" + PowMod.powmod(num, 2, base); |
return (quadrat.endsWith("" + num)); |
} |
private static void checkBase(int b) { |
Vector<String> roots = new Vector<String>(); |
for (int i = 0; i < b; i++) { |
if (isImmortal(i, b)) { |
roots.add("" + i); |
} |
} |
System.out.println("Base " + b + ": " + roots); |
} |
public static void main(String[] args) { |
for (int i = 1; i < 255; i++) { |
checkBase(i); |
} |
} |
} |