# cycling

## 计算$\lambda(n)$

h+1易分解为17个小素数，且没有2次及以上的素数

# benaloh

public key cryptosystems， which is homomorphic.

## Key Generation

Given block size r, a public/private key pair is generated as follows:

1. Choose large primes p and q such that r | (p-1), gcd(r, (p-1)/r) = 1, and gcd (r,(q - 1)) = 1;

2. set $n = pq, \phi = (p-1)(q-1)$

3. Note: If r is composite, it was pointed out by Fousse et al. in 2011that the above conditions (i.e., those stated in the original paper) are insufficient to guarantee correct decryption

4. Set $x\;=\;y^{\phi/r}\;mod\;n$

The public key is then ${\displaystyle y,n}$, and the private key is ${\displaystyle \phi ,x}$

## Message Encryption

To encrypt message $m\in Z_r$:

1. Choose a random $u \in Z{_n^*}$;
2. set $E_r(m) = y^mu^r\;mod\;n$

## Message Decryption

To decrypt message $c\in Z{_n^*}$:

1. comupte $a = c ^{\phi/r} \;mod n$
2. output $m = log_x(a)$, i.e.,find m such that $x^m \;\equiv1 \; mod n$

Baby-step giant-step algorithm can be used to recover m in $O(\sqrt{r})$ time and space