import java.math.BigInteger;
/**
*
欧拉函数:
定义：用于计算 p(n)，比n小的所有与n互质的数。
计算公式：p(n)=n*(1-1/p1)*(1-1/p2)....*(1-1/pk)【p1,p2,pk都是n的素因子】
另：若n=p1^q1*p2^q2*.....*pk^qk
则，p(n)=(p1-1)*p1^(q1-1)*(p1-1)*p2^(q2-1)......*(pk-1)*pk^(qk-1)
性质：若m,n互质，φ(mn)=φ(m)φ(n)。当n为奇数时，φ(2n)=φ(n)
欧拉定理：
a,m互质，a^φ(m)≡1(mod m)
例：2,3互质，那么，2^2%3=1
推论：对于互质的数a、n，满足a^(φ(n)+1) ≡ a (mod n)
费马小定理：
假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1
费马大定理：
当整数n > 2时，关于x, y, z的不定方程 x^n + y^n = z^n. 无正整数解
威尔逊定理：
当仅当p是素数：( p -1 )! ≡ -1 ( mod p )
//Question:http://www.qlcoder.com/task/7683
*/
public class Test {
static String msg = "hello oreo";
static int exponent = 65537;
static BigInteger modulus = new java.math.BigInteger(
"41031587223377599579245988781518671358060455361860183212406274189493280555347897");
static String decodeMsg = "14a091645d307b8abd8632a1fb83f81e38c1b33d3286ca814a5742bec52c4b06d08";
public static void main(String[] args) {
System.out.println("encode---");
encode(msg);
System.out.println("decode---");
decode(decodeMsg);
}
/**
* 按照题目说明，正向加密
*/
public static void encode(String msg) {
// 先将明文转为16进制
String hex = convertStringToHex(msg);
System.out.println("hex=" + hex);
// 再将明文16进制转为10进制
BigInteger ten = new BigInteger(hex, 16);
System.out.println("ten=" + ten);
// 计算明文10进制的exponent次方再模上modulus,得到10进制结果
BigInteger resultTen = ten.pow(exponent).mod(modulus);
System.out.println("resultTen=" + resultTen);
// 将结果转为16进制
System.out.println("resultSixteen" + resultTen.toString(16));
}
public static void decode(String encodeMsg) {
BigInteger decodeTen = new BigInteger(decodeMsg, 16);//
System.out.println("decodTen=" + decodeTen);
//分解质因数用：http://factordb.com/
BigInteger p1=new BigInteger("5991810554633396517767024967580894321152");
BigInteger q1=new BigInteger("6847944682037444681162770672798288913848");
BigInteger eulerModulus=p1.multiply(q1);
System.out.println("eulerModulus="+eulerModulus);
BigInteger d = new BigInteger(String.valueOf(exponent))
.modInverse(new BigInteger(String.valueOf(eulerModulus)));
System.out.println("e对于φ(n)的模反元素d：" + d);
BigInteger resultTen=decodeTen.pow(d.intValue()).mod(modulus);
System.out.println(resultTen);
String resultSixteen=resultTen.toString(16);
System.out.println(resultSixteen);
System.out.println(convertHexToString(resultSixteen));
}
public static String convertStringToHex(String str) {
char[] chars = str.toCharArray();
StringBuffer hex = new StringBuffer();
for (int i = 0; i < chars.length; i++) {
hex.append(Integer.toHexString((int) chars[i]));
}
return hex.toString();
}
public static String convertHexToString(String hex) {
StringBuilder sb = new StringBuilder();
StringBuilder temp = new StringBuilder();
// 49204c6f7665204a617661 split into two characters 49, 20, 4c...
for (int i = 0; i < hex.length() - 1; i += 2) {
// grab the hex in pairs
String output = hex.substring(i, (i + 2));
// convert hex to decimal
int decimal = Integer.parseInt(output, 16);
// convert the decimal to character
sb.append((char) decimal);
temp.append(decimal);
}
return sb.toString();
}
/**
* 欧拉函数 在数论中，对正整数n，欧拉函数φ (n)是小于或等于n的正整数中与n互质的数的数目。
* 此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。
*
* 在数论中，欧拉定理（也称费马-欧拉定理或欧拉phi函数定理）是一个关于同余的性质。
* 欧拉定理表明，若n,a为正整数，且n,a互素（即gcd(a,n)=1，则 a^φ(n)=1 (mod n) 即
* a^φ(n)与1在模n下同余；φ(n)为欧拉函数。 欧拉定理得名于瑞士数学家莱昂哈德·欧拉。 欧拉定理实际上是费马小定理的推广。
*
* 首先看一个基本的例子。令a=3,n=5,此两数为互质正整数。 小于等于5的正整数中与5互质的数有4个（1、2、3和4），所以 φ(5)=4
* 计算a^φ(n)=3^4=81=1(mod 5)与定理结果相符。 使用本定理可大程度地简化幂的模运算。比如计算7^222的个位数时，
* 可将此命题视为求7^222被10除的余数：因7和10互质，且φ(10)=4, 故由欧拉定理可知7^4=1 (mod 10),所以
* 7^222=7^(4*55+2)=7^4^55*7^2=1^55*7^2=49=9 (mod 10)
* 一般在简化幂的模运算的时候，当a和n互质时，可对a的指数取模φ(n): a^x=a^y (mod n) ,其中x=y(mod φ(n))
*/
}
