Захаров Александр Владимирович

Математика, высшая математика, дискретная математика, математический анализ, подготовка к олимпиадам, …

Выполнено заказов: 65, отзывов: 35, оценка: 4,87+

Россия, Москва

Вопросов	0
Ответов	2
Рейтинг	0

Ответы:

👍
0
👎

Ответ на «RSA»

Well... Putting this mash in simple terms, assuming that $m\in Z/p+Z/q$ is invertible, you just saying that a cyclic subgroup of $(Z/p+Z/q)^$ generated by $e$ is finite. Surely, its order divides $l.c.m(p-1,q-1)=|(Z/p+Z/q)^|$. Thus, after that number of steps, the sequence, you will see, starts to repeat. Abstractly $(Z/p+Z/q)^*$ is isomorphic to $Z/(p-1)+Z/(q-1)$ and for general primes $p,q>2$ $g.c.d(p-1,q-1)=2$, hence there is a message $m$ for which you have to run your procedure $(p-1)(q-1)/2$ times until you reach the original message and find the closed key using this particulal $m$.
You may ask then, what is expected number of steps for various m's. Again, abstractly $(Z/p+Z/q)^*$ is isomorphic to $Z/(p-1)+Z/(q-1)$ and the mean size of a cyclic subgroup generated by $m$, though has no closed expression, has an order equal to O(pq) (whatsever this mean for $p,q$ being fixed).

Захаров Александр Владимирович 02 май 2021 22:13

👍
0
👎

Ответ на «Number theory nujna pomosh»

Unfortunately this engine does not support TeX, sorry for the bad handwriting.

In fact RSA works for all $P\in Z/p+Z/q$.
If P is invertible in the ring Z/p+Z/q, then $P^{d e}=P mod n$ by the construction: $de=1 mod \phi(n)$, where Euler function $\phi(n)=|(Z/p+Z/q)^*|$ is equal to the number of invertible elements of the ring. Here $d,e$ is a pair of decryption/encryption keys. Hence we can exploit the fact that $P^\phi(n)=1 mod n$ to show that $P^{de}=P mod n$.
If P is not invertible, then $P^\phi(pq)$ is not equal to 1 in the ring, nonetheless $P^{d e}=P mod n$. For example, if $P=(0,a)\in Z/p+Z/q$, then $P^{\phi(n)}=(0,1)$, thus $P^{de}=P mod n$ and the desired equality holds.

Захаров Александр Владимирович 02 май 2021 21:21