We work with the RSA modulus \(n=pq\) for the specific primes \(p=1009\) and \(q=3643\). A public exponent \(e\) is valid when
$$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$
A message \(m\in\{0,1,\dots,n-1\}\) is called unconcealed if encryption leaves it unchanged:
$$m^e \equiv m \pmod n.$$
The goal is to find all valid exponents that minimize the number of unconcealed messages and then add those exponents together.
The important observation is that we never need to test every message for every exponent. For a fixed \(e\), the number of fixed points of the map \(x\mapsto x^e \pmod n\) has a simple closed form, and that form depends only on two gcd values.
First work modulo a prime \(r\), where \(r\) is either \(p\) or \(q\). The congruence
$$x^e \equiv x \pmod r$$
can be rewritten as
$$x(x^{e-1}-1)\equiv 0 \pmod r.$$
So every solution is either \(x=0\) or a nonzero residue satisfying \(x^{e-1}=1\). The nonzero residues modulo \(r\) form a cyclic multiplicative group of size \(r-1\). In a cyclic group of order \(r-1\), the equation \(y^k=1\) has exactly \(\gcd(k,r-1)\) solutions. Therefore the number of unconcealed residues modulo \(r\) is
$$N_r(e)=\gcd(e-1,r-1)+1.$$
The extra \(+1\) is the zero solution.
A residue class modulo \(n=pq\) is unconcealed exactly when its reductions modulo \(p\) and modulo \(q\) are both unconcealed. Because \(p\) and \(q\) are distinct primes, the Chinese Remainder Theorem gives a one-to-one correspondence between pairs of residues modulo \(p\) and \(q\) and residues modulo \(n\). Hence
$$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$$
This is the central invariant of the problem. Once it is known, the original task is no longer about testing messages; it is about understanding how small the two gcd factors can be.
Since \(p\) and \(q\) are odd primes, both \(p-1\) and \(q-1\) are even, so \(\varphi(n)\) is even as well. Any valid RSA exponent must satisfy \(\gcd(e,\varphi(n))=1\), which forces \(e\) to be odd. Therefore \(e-1\) is even, and both gcd terms are at least 2:
$$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$$
That immediately yields
$$N(e)\ge (2+1)(2+1)=9.$$
So 9 is the smallest unconcealed-message count any valid exponent could possibly have. The remaining question is whether the concrete primes \(1009\) and \(3643\) actually allow this lower bound to be reached.
For the problem data we have
$$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$$
To attain the lower bound 9, both gcd factors must be exactly 2. So the optimal exponents are precisely the valid \(e\) such that
$$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2.$$
Equivalently, \(e-1\) must be even but not divisible by any of the odd prime factors \(3\), \(7\), or \(607\). This description is mathematically sharper than a brute-force message count, but it is the same quantity the implementation evaluates for every candidate exponent.
The sample mentioned in the problem statement uses \(p=19\), \(q=37\), and \(e=181\). Then
$$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$$
so
$$N(181)=(18+1)(36+1)=703=19\cdot 37.$$
In other words, every message is unconcealed in that sample.
For the actual target primes, take \(e=11\). It is valid because \(\gcd(11,\varphi(n))=1\), and
$$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2.$$
Therefore
$$N(11)=(2+1)(2+1)=9,$$
so the lower bound is attained. By contrast, \(e=5\) is also valid, but
$$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$$
which gives \(N(5)=15\). This makes the optimization criterion completely explicit: minimize the gcd factors, not the size of \(e\).
The C++, Python, and Java implementations all follow the same compact strategy. They fix the two primes, compute \(\varphi(n)=(p-1)(q-1)\), and iterate through every integer \(e\) with \(2 \le e \lt \varphi(n)\).
Inside that loop, the RSA validity condition is checked first: only exponents with \(\gcd(e,\varphi(n))=1\) are kept. For each valid exponent, the implementation evaluates
$$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big)$$
directly, compares it with the best value seen so far, and updates the running sum of exponents that achieve the current minimum.
The C++ implementation also performs small sanity checks before the final scan. It compares the closed form with brute-force modular exponentiation on tiny prime pairs and confirms the stated sample count for \(p=19\), \(q=37\), and \(e=181\). Those checks do not alter the main algorithm; they only verify that the formula matches the underlying RSA fixed-point count.
There are \(\varphi(n)-2\) candidates in the outer scan. Each candidate requires only a constant number of gcd computations, and each gcd uses the Euclidean algorithm in \(O(\log n)\) time. The total running time is therefore
$$O(\varphi(n)\log n).$$
The extra memory usage is \(O(1)\), since the implementation stores only a few integers for the current candidate, the best unconcealed count, and the accumulated sum. This is far better than checking all \(n\) messages for every valid exponent.
Wir betrachten den RSA-Modulus \(n=pq\) mit den konkreten Primzahlen \(p=1009\) und \(q=3643\). Ein öffentlicher Exponent \(e\) ist genau dann zulässig, wenn
$$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$
Eine Nachricht \(m\in\{0,1,\dots,n-1\}\) heißt unverschleiert, wenn die Verschlüsselung sie nicht verändert:
$$m^e \equiv m \pmod n.$$
Gesucht ist die Summe aller zulässigen Exponenten, für die die Anzahl solcher unverschleierten Nachrichten minimal ist.
Man muss nicht für jedes \(e\) alle Nachrichten ausprobieren. Für einen festen Exponenten lässt sich die Anzahl der Fixpunkte der Abbildung \(x\mapsto x^e \pmod n\) in geschlossener Form angeben, und diese Form hängt nur von zwei ggT-Werten ab.
Zuerst arbeiten wir modulo einer Primzahl \(r\), also entweder \(r=p\) oder \(r=q\). Die Kongruenz
$$x^e \equiv x \pmod r$$
ist äquivalent zu
$$x(x^{e-1}-1)\equiv 0 \pmod r.$$
Jede Lösung ist also entweder \(x=0\) oder ein von null verschiedener Rest mit \(x^{e-1}=1\). Die von null verschiedenen Klassen modulo \(r\) bilden eine zyklische multiplikative Gruppe der Ordnung \(r-1\). In einer zyklischen Gruppe der Ordnung \(r-1\) besitzt die Gleichung \(y^k=1\) genau \(\gcd(k,r-1)\) Lösungen. Daher gilt
$$N_r(e)=\gcd(e-1,r-1)+1.$$
Das zusätzliche \(+1\) stammt von der Lösung \(x=0\).
Eine Restklasse modulo \(n=pq\) ist genau dann unverschleiert, wenn ihre Reduktionen modulo \(p\) und modulo \(q\) beide unverschleiert sind. Weil \(p\) und \(q\) verschieden sind, liefert der Chinesische Restsatz eine Bijektion zwischen Paaren von Restklassen modulo \(p\) und \(q\) und Restklassen modulo \(n\). Somit ist
$$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$$
Das ist die zentrale Invariante des Problems. Sobald diese Formel feststeht, reduziert sich die Aufgabe auf die Frage, wie klein die beiden ggT-Faktoren werden können.
Da \(p\) und \(q\) ungerade Primzahlen sind, sind sowohl \(p-1\) als auch \(q-1\) gerade, also ist auch \(\varphi(n)\) gerade. Aus \(\gcd(e,\varphi(n))=1\) folgt dann, dass ein zulässiges \(e\) ungerade sein muss. Damit ist \(e-1\) gerade, und beide ggT-Terme sind mindestens 2:
$$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$$
Also gilt sofort
$$N(e)\ge (2+1)(2+1)=9.$$
Die Zahl 9 ist also die kleinstmögliche Anzahl unverschleierter Nachrichten für einen gültigen Exponenten. Es bleibt nur zu zeigen, wann diese Schranke bei den konkreten Primzahlen tatsächlich erreicht wird.
Für die gegebenen Primzahlen zerfallen die beiden Werte zu
$$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$$
Um die Untergrenze 9 zu erreichen, müssen beide ggT-Werte genau 2 sein. Die optimalen Exponenten sind also genau die zulässigen \(e\) mit
$$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2.$$
Äquivalent dazu ist \(e-1\) zwar gerade, aber durch keinen der ungeraden Primfaktoren \(3\), \(7\) oder \(607\) teilbar. Diese Beschreibung ist mathematisch präziser als ein naives Durchzählen aller Nachrichten, aber sie ist exakt dieselbe Größe, die die Implementierungen für jeden Kandidaten auswerten.
Das Beispiel aus der Aufgabenstellung nimmt \(p=19\), \(q=37\) und \(e=181\). Dann gilt
$$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$$
also
$$N(181)=(18+1)(36+1)=703=19\cdot 37.$$
Dort ist also tatsächlich jede Nachricht unverschleiert.
Für die eigentlichen Zielprimzahlen ist \(e=11\) ein Beispiel für einen optimalen Exponenten. Er ist zulässig und erfüllt
$$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2,$$
woraus
$$N(11)=(2+1)(2+1)=9$$
folgt. Dagegen ist \(e=5\) zwar ebenfalls zulässig, aber
$$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$$
sodass \(N(5)=15\) ist. Das Optimierungskriterium lautet also nicht „kleines \(e\)“, sondern „möglichst kleine ggT-Faktoren“.
Die C++-, Python- und Java-Implementierungen verwenden denselben knappen Ablauf. Sie setzen die beiden Primzahlen fest, berechnen \(\varphi(n)=(p-1)(q-1)\) und iterieren anschließend über alle ganzen Zahlen \(e\) mit \(2 \le e \lt \varphi(n)\).
In dieser Schleife wird zuerst die RSA-Bedingung \(\gcd(e,\varphi(n))=1\) geprüft. Für jedes zulässige \(e\) berechnet die Implementierung dann direkt
$$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big),$$
vergleicht diesen Wert mit dem bisher kleinsten und aktualisiert die laufende Summe aller Exponenten, die das aktuelle Minimum erreichen.
Die C++-Version enthält zusätzlich kleine Plausibilitätsprüfungen. Dabei wird die geschlossene Formel auf sehr kleinen Primzahlpaaren mit einer Brute-Force-Auswertung per modularer Exponentiation verglichen und außerdem das Beispiel \(p=19\), \(q=37\), \(e=181\) verifiziert. Am eigentlichen Algorithmus ändert das nichts; es bestätigt nur die Herleitung vor dem endgültigen Durchlauf.
Der äußere Durchlauf betrachtet \(\varphi(n)-2\) Kandidaten. Pro Kandidat werden nur konstant viele ggT-Berechnungen benötigt, und jeder ggT kostet mit dem euklidischen Algorithmus \(O(\log n)\). Insgesamt ergibt sich also
$$O(\varphi(n)\log n).$$
Der zusätzliche Speicherbedarf ist \(O(1)\), da nur wenige Ganzzahlen für den aktuellen Kandidaten, das bisherige Minimum und die aufsummierten Exponenten gehalten werden. Gegenüber einer Brute-Force-Prüfung aller \(n\) Nachrichten für jedes gültige \(e\) ist das ein massiver Gewinn.
Burada RSA modülü \(n=pq\) olup asal sayılar \(p=1009\) ve \(q=3643\) olarak verilmiştir. Bir açık anahtar üssü \(e\), ancak şu koşulları sağlıyorsa geçerlidir:
$$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$
\(m\in\{0,1,\dots,n-1\}\) mesajı, şifreleme onu değiştirmiyorsa unconcealed kabul edilir:
$$m^e \equiv m \pmod n.$$
İstenen şey, unconcealed mesaj sayısını en aza indiren tüm geçerli üsleri bulup bu üsleri toplamaktır.
Asıl püf nokta, her \(e\) için bütün mesajları tek tek denemek zorunda olmamamızdır. Sabit bir \(e\) için \(x\mapsto x^e \pmod n\) dönüşümünün kaç sabit noktası olduğunu kapalı formülle yazabiliyoruz; bu formül de yalnızca iki tane EBOB değerine bağlıdır.
Önce asal bir mod \(r\) üzerinde çalışalım; burada \(r\), ya \(p\) ya da \(q\) olacaktır. Şu denklem
$$x^e \equiv x \pmod r$$
şuna eşdeğerdir:
$$x(x^{e-1}-1)\equiv 0 \pmod r.$$
Dolayısıyla her çözüm ya \(x=0\) olmalıdır ya da \(x^{e-1}=1\) denklemini sağlayan sıfırdan farklı bir kalandır. Modulo \(r\) altında sıfır dışındaki kalıntılar, büyüklüğü \(r-1\) olan çevrimsel bir çarpma grubu oluşturur. Çevrimsel bir grupta \(y^k=1\) denkleminin çözüm sayısı tam olarak \(\gcd(k,r-1)\) olur. Bu yüzden
$$N_r(e)=\gcd(e-1,r-1)+1$$
elde edilir. Buradaki \(+1\), \(x=0\) çözümünden gelir.
Bir sayı modulo \(n=pq\) altında ancak ve ancak hem modulo \(p\) hem de modulo \(q\) altında unconcealed ise modulo \(n\) altında da unconcealed olur. \(p\) ile \(q\) farklı asal olduğundan, Çin Kalan Teoremi modulo \(p\) ve modulo \(q\) kalıntı çiftleri ile modulo \(n\) kalıntıları arasında bire bir eşleme verir. Böylece toplam unconcealed mesaj sayısı
$$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big)$$
olur. Problemin merkezi formülü budur. Bundan sonra mesele mesaj saymak değil, bu iki EBOB çarpanını olabildiğince küçültmektir.
\(p\) ve \(q\) tek asal sayılar olduğu için \(p-1\) ve \(q-1\) çift sayıdır; dolayısıyla \(\varphi(n)\) de çifttir. \(\gcd(e,\varphi(n))=1\) koşulu geçerli bir RSA üssünün tek olmasını zorunlu kılar. Bu da \(e-1\)'in çift olduğu anlamına gelir. O halde her iki EBOB terimi de en az 2'dir:
$$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$$
Buradan hemen
$$N(e)\ge (2+1)(2+1)=9$$
çıkar. Yani herhangi bir geçerli üs için ulaşılabilecek en küçük unconcealed mesaj sayısı 9'dur. Geriye kalan soru, verilen asal sayılarda bu alt sınırın gerçekten elde edilip edilemeyeceğidir.
Bu problemde
$$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$$
Alt sınır olan 9'a ulaşmak için her iki EBOB değerinin de tam olarak 2 olması gerekir. Demek ki optimal üsler, şu koşulları sağlayan geçerli \(e\) değerleridir:
$$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2.$$
Başka bir deyişle \(e-1\) çift olmalı ama \(3\), \(7\) ve \(607\) gibi tek asal çarpanlardan hiçbirine bölünmemelidir. Bu bakış açısı, kaba kuvvetle mesaj denemekten çok daha bilgilendiricidir; yine de programın kullandığı büyüklük tam olarak budur.
Sorudaki örnek \(p=19\), \(q=37\) ve \(e=181\) içindir. Bu durumda
$$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$$
dolayısıyla
$$N(181)=(18+1)(36+1)=703=19\cdot 37.$$
Yani örnekte bütün mesajlar unconcealed kalır.
Asıl hedef asal sayılar için \(e=11\) iyi bir örnektir. Bu üs geçerlidir ve
$$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2$$
olduğundan
$$N(11)=(2+1)(2+1)=9$$
elde edilir; yani alt sınır gerçekten sağlanır. Buna karşılık \(e=5\) de geçerlidir ama
$$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$$
bu yüzden \(N(5)=15\) olur. Dolayısıyla optimize edilen şey üssün küçüklüğü değil, iki EBOB çarpanının küçüklüğüdür.
C++, Python ve Java uygulamaları aynı kısa planı izler. Önce iki asal sayı sabitlenir, sonra \(\varphi(n)=(p-1)(q-1)\) hesaplanır ve \(2 \le e \lt \varphi(n)\) aralığındaki tüm tamsayılar taranır.
Döngü içinde önce RSA geçerlilik koşulu kontrol edilir: yalnızca \(\gcd(e,\varphi(n))=1\) olan üsler dikkate alınır. Her geçerli üs için uygulama şu kapalı formülü doğrudan hesaplar:
$$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$$
Daha sonra bu değer o ana kadarki en iyi değerle karşılaştırılır ve minimumu sağlayan üslerin toplamı güncellenir.
C++ uygulaması ayrıca küçük doğrulama kontrolleri de içerir. Çok küçük asal çiftlerinde formülü brute-force modular exponentiation ile karşılaştırır ve \(p=19\), \(q=37\), \(e=181\) örneğini doğrular. Bu kontroller ana algoritmayı değiştirmez; sadece türetimin doğru uygulandığını gösterir.
Dış döngü \(\varphi(n)-2\) aday üs inceler. Her aday için sabit sayıda EBOB hesabı gerekir ve her EBOB, Öklid algoritmasıyla \(O(\log n)\) zamanda bulunur. Bu nedenle toplam süre
$$O(\varphi(n)\log n)$$
olur. Ek bellek kullanımı ise \(O(1)\)'dir; çünkü yalnızca birkaç tamsayı tutulur. Bu yaklaşım, her geçerli üs için bütün \(n\) mesajı denemeye göre çok daha etkilidir.
Trabajamos con el módulo RSA \(n=pq\) para los primos concretos \(p=1009\) y \(q=3643\). Un exponente público \(e\) es válido cuando
$$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$
Un mensaje \(m\in\{0,1,\dots,n-1\}\) se llama no ocultado si el cifrado no lo cambia:
$$m^e \equiv m \pmod n.$$
La meta es sumar todos los exponentes válidos que minimizan la cantidad de mensajes no ocultados.
La idea decisiva es que no hace falta probar todos los mensajes para cada exponente. Para un \(e\) fijo, el número de puntos fijos de la transformación \(x\mapsto x^e \pmod n\) tiene una fórmula cerrada, y esa fórmula depende solamente de dos máximos comunes divisores.
Primero trabajemos módulo un primo \(r\), donde \(r\) puede ser \(p\) o \(q\). La congruencia
$$x^e \equiv x \pmod r$$
se reescribe como
$$x(x^{e-1}-1)\equiv 0 \pmod r.$$
Por tanto, cada solución es o bien \(x=0\), o bien un residuo no nulo que satisface \(x^{e-1}=1\). Los residuos no nulos módulo \(r\) forman un grupo multiplicativo cíclico de tamaño \(r-1\). En un grupo cíclico de orden \(r-1\), la ecuación \(y^k=1\) tiene exactamente \(\gcd(k,r-1)\) soluciones. En consecuencia, el número de residuos no ocultados módulo \(r\) es
$$N_r(e)=\gcd(e-1,r-1)+1.$$
El término \(+1\) corresponde a la solución \(x=0\).
Una clase residual módulo \(n=pq\) es no ocultada si y solo si sus reducciones módulo \(p\) y módulo \(q\) también lo son. Como \(p\) y \(q\) son primos distintos, el Teorema Chino del Resto da una biyección entre los pares de residuos módulo \(p\) y \(q\) y los residuos módulo \(n\). Por ello, el total de mensajes no ocultados es
$$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$$
Éste es el invariante central del problema. A partir de aquí, la búsqueda ya no consiste en revisar mensajes uno por uno, sino en entender cuán pequeños pueden ser esos dos factores gcd.
Como \(p\) y \(q\) son primos impares, tanto \(p-1\) como \(q-1\) son pares, y por lo tanto \(\varphi(n)\) también es par. La condición \(\gcd(e,\varphi(n))=1\) obliga a que \(e\) sea impar. Entonces \(e-1\) es par y ambos gcd son por lo menos 2:
$$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$$
Se obtiene de inmediato
$$N(e)\ge (2+1)(2+1)=9.$$
Así, 9 es la menor cantidad posible de mensajes no ocultados para un exponente RSA válido. Falta ver cuándo esa cota se alcanza con los primos concretos del problema.
Para los datos reales del problema,
$$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$$
Para alcanzar la cota 9, ambos factores gcd deben ser exactamente 2. Por tanto, los exponentes óptimos son precisamente los \(e\) válidos tales que
$$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2.$$
Equivale a decir que \(e-1\) debe ser par pero no múltiplo de ninguno de los factores primos impares \(3\), \(7\) o \(607\). Esta caracterización es más informativa que un conteo ingenuo de mensajes, aunque la implementación evalúa exactamente esta misma cantidad para cada candidato.
El ejemplo del enunciado usa \(p=19\), \(q=37\) y \(e=181\). Entonces
$$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$$
de modo que
$$N(181)=(18+1)(36+1)=703=19\cdot 37.$$
Es decir, en ese ejemplo todos los mensajes quedan sin ocultar.
Para los primos objetivo, \(e=11\) es un ejemplo óptimo. Es válido y satisface
$$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2,$$
por lo que
$$N(11)=(2+1)(2+1)=9.$$
En cambio, \(e=5\) también es válido, pero
$$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$$
y eso produce \(N(5)=15\). El criterio de optimización, por tanto, no es que \(e\) sea pequeño, sino que los dos factores gcd sean lo más pequeños posible.
Las implementaciones en C++, Python y Java siguen el mismo plan. Fijan los dos primos, calculan \(\varphi(n)=(p-1)(q-1)\) y recorren todos los enteros \(e\) con \(2 \le e \lt \varphi(n)\).
Dentro de ese recorrido se comprueba primero la condición RSA \(\gcd(e,\varphi(n))=1\). Para cada exponente válido, la implementación evalúa directamente
$$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big),$$
lo compara con el mejor valor observado hasta ese momento y actualiza la suma acumulada de exponentes que alcanzan el mínimo actual.
La implementación en C++ además incluye pequeñas verificaciones de consistencia. Contrasta la fórmula cerrada con una comprobación por exponenciación modular en ejemplos diminutos y confirma el conteo del caso \(p=19\), \(q=37\), \(e=181\). Esas comprobaciones no cambian el algoritmo principal; solo validan la derivación antes del barrido final.
El recorrido externo considera \(\varphi(n)-2\) candidatos. Cada candidato necesita solo un número constante de cálculos de gcd, y cada gcd cuesta \(O(\log n)\) con el algoritmo de Euclides. Por lo tanto, el tiempo total es
$$O(\varphi(n)\log n).$$
La memoria adicional es \(O(1)\), ya que solo se guardan unas pocas variables enteras. Esto es muchísimo mejor que revisar los \(n\) mensajes para cada exponente válido.
本题讨论的 RSA 模数是 \(n=pq\)，其中具体素数为 \(p=1009\)、\(q=3643\)。公开指数 \(e\) 必须满足
$$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$
如果消息 \(m\in\{0,1,\dots,n-1\}\) 在加密后保持不变，即
$$m^e \equiv m \pmod n,$$
那么它就称为 unconcealed message。题目要求找出所有使 unconcealed message 数量最小的合法指数 \(e\)，并把这些 \(e\) 全部求和。
真正关键的地方在于：我们完全不需要对每个 \(e\) 去枚举所有消息。对固定的指数 \(e\)，映射 \(x\mapsto x^e \pmod n\) 的不动点个数可以写成一个闭式公式，而这个公式只依赖于两个 gcd 值。
先在素数模 \(r\) 下分析，其中 \(r\) 可以是 \(p\) 或 \(q\)。方程
$$x^e \equiv x \pmod r$$
可改写为
$$x(x^{e-1}-1)\equiv 0 \pmod r.$$
因此任何解都分成两类：一类是 \(x=0\)，另一类是满足 \(x^{e-1}=1\) 的非零解。模 \(r\) 的非零剩余类构成一个大小为 \(r-1\) 的循环乘法群。在一个阶为 \(r-1\) 的循环群中，方程 \(y^k=1\) 恰好有 \(\gcd(k,r-1)\) 个解。所以模 \(r\) 下 unconcealed residue 的数量为
$$N_r(e)=\gcd(e-1,r-1)+1.$$
其中额外的 \(+1\) 正是来自解 \(x=0\)。
一个数模 \(n=pq\) 不动，当且仅当它模 \(p\) 和模 \(q\) 都是不动点。由于 \(p\) 与 \(q\) 是不同素数，中国剩余定理告诉我们：模 \(p\) 的剩余与模 \(q\) 的剩余的有序对，与模 \(n\) 的剩余类之间存在一一对应。因此总的 unconcealed message 数量就是两个方向解数的乘积：
$$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$$
这就是整道题最核心的不变量。一旦得到这个公式，问题就从“对每个指数逐个检查消息”转化成“研究两个 gcd 因子能压到多小”。
因为 \(p\) 和 \(q\) 都是奇素数，所以 \(p-1\) 与 \(q-1\) 都是偶数，\(\varphi(n)\) 也必然是偶数。合法 RSA 指数必须与 \(\varphi(n)\) 互素，因此 \(e\) 一定是奇数，于是 \(e-1\) 一定是偶数。这样两个 gcd 项至少都是 2：
$$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$$
于是立刻得到
$$N(e)\ge (2+1)(2+1)=9.$$
也就是说，不论怎样选合法指数，unconcealed message 的数量都不可能低于 9。接下来只需要判断在本题给定的具体素数下，这个下界能否真正达到。
把数据展开可得
$$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$$
如果要达到下界 9，就必须让两个 gcd 都恰好等于 2。因此最优指数恰好是那些满足
$$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2$$
的合法 \(e\)。换句话说，\(e-1\) 必须是偶数，但不能再被任何奇质因子 \(3\)、\(7\)、\(607\) 整除。这个刻画比直接暴力统计消息数量更清楚，但实现里计算的正是这个量。
题目陈述中的示例是 \(p=19\)、\(q=37\)、\(e=181\)。这时
$$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$$
因此
$$N(181)=(18+1)(36+1)=703=19\cdot 37.$$
这说明该示例中所有消息都会保持不变，也就是全部都是 unconcealed messages。
对于本题目标素数，\(e=11\) 是一个达到最优值的简单例子。它满足 RSA 合法性条件，并且
$$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2,$$
所以
$$N(11)=(2+1)(2+1)=9.$$
这表明下界确实可以达到。相反，\(e=5\) 虽然也是合法指数，但
$$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$$
于是 \(N(5)=15\)。可见真正要最小化的不是指数本身，而是两个 gcd 因子。
C++、Python 和 Java 实现遵循完全相同的思路。它们先固定两个素数，计算 \(\varphi(n)=(p-1)(q-1)\)，然后遍历所有满足 \(2 \le e \lt \varphi(n)\) 的整数。
在遍历过程中，首先检查 \(\gcd(e,\varphi(n))=1\)，只有满足这条 RSA 条件的指数才会继续处理。对于每个合法 \(e\)，实现都会直接计算
$$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big),$$
并把它与当前最优值比较。如果得到更小的 unconcealed 数量，就重置最优和答案和；如果得到相同的最优值，就把这个 \(e\) 加入总和。
C++ 实现还额外做了小规模正确性检查。它在很小的素数对上用直接模幂枚举来核对闭式公式，并验证了示例 \(p=19\)、\(q=37\)、\(e=181\) 的结果。这些检查只是确认公式推导无误，不改变最终的主算法。
外层遍历的候选数是 \(\varphi(n)-2\) 个。每个候选只需要常数次 gcd 计算，而欧几里得算法求 gcd 的时间是 \(O(\log n)\)。因此总时间复杂度为
$$O(\varphi(n)\log n).$$
额外空间复杂度是 \(O(1)\)，因为实现只维护少量整数变量。与“对每个合法指数都枚举全部 \(n\) 个消息”的暴力方案相比，这已经是数量级上的改进。
Рассматривается RSA-модуль \(n=pq\) для конкретных простых чисел \(p=1009\) и \(q=3643\). Открытая экспонента \(e\) допустима тогда и только тогда, когда
$$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$
Сообщение \(m\in\{0,1,\dots,n-1\}\) называется unconcealed, если шифрование оставляет его без изменения:
$$m^e \equiv m \pmod n.$$
Нужно найти все допустимые экспоненты, минимизирующие число таких сообщений, и затем просуммировать эти экспоненты.
Главная идея состоит в том, что не нужно для каждого \(e\) перебирать все сообщения. Для фиксированной экспоненты число неподвижных точек отображения \(x\mapsto x^e \pmod n\) выражается замкнутой формулой, зависящей только от двух значений gcd.
Сначала рассмотрим простое \(r\), где \(r\) равно либо \(p\), либо \(q\). Сравнение
$$x^e \equiv x \pmod r$$
переписывается как
$$x(x^{e-1}-1)\equiv 0 \pmod r.$$
Значит, любое решение либо равно нулю, либо является ненулевым вычетом, удовлетворяющим \(x^{e-1}=1\). Ненулевые классы по модулю \(r\) образуют циклическую мультипликативную группу порядка \(r-1\). В циклической группе порядка \(r-1\) уравнение \(y^k=1\) имеет ровно \(\gcd(k,r-1)\) решений. Следовательно, число unconcealed-вычетов по модулю \(r\) равно
$$N_r(e)=\gcd(e-1,r-1)+1.$$
Добавка \(+1\) отвечает решению \(x=0\).
Класс вычетов по модулю \(n=pq\) является неподвижным тогда и только тогда, когда он неподвижен и по модулю \(p\), и по модулю \(q\). Поскольку \(p\) и \(q\) различны, китайская теорема об остатках дает биекцию между парами вычетов по модулям \(p\) и \(q\) и вычетами по модулю \(n\). Поэтому общее число unconcealed-сообщений равно
$$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$$
Это и есть центральный инвариант задачи. После этого поиск сводится уже не к перебору сообщений, а к анализу того, насколько малыми могут быть два множителя gcd.
Так как \(p\) и \(q\) являются нечетными простыми, числа \(p-1\) и \(q-1\) четны, а значит \(\varphi(n)\) тоже четно. Условие \(\gcd(e,\varphi(n))=1\) заставляет допустимую RSA-экспоненту быть нечетной. Тогда \(e-1\) четно, и оба gcd-множителя не меньше 2:
$$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$$
Отсюда немедленно следует
$$N(e)\ge (2+1)(2+1)=9.$$
Итак, 9 является наименьшим возможным числом unconcealed-сообщений для допустимой экспоненты. Остается понять, когда эта нижняя граница достигается для конкретных простых \(1009\) и \(3643\).
Для данных задачи имеем разложения
$$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$$
Чтобы достичь значения 9, оба gcd должны быть ровно равны 2. Следовательно, оптимальные экспоненты - это в точности те допустимые \(e\), для которых
$$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2.$$
Эквивалентно, число \(e-1\) должно быть четным, но не делиться ни на один из нечетных простых множителей \(3\), \(7\) и \(607\). Такая формулировка дает полную математическую картину и в точности соответствует величине, которую реализация вычисляет для каждого кандидата.
Пример из условия использует \(p=19\), \(q=37\) и \(e=181\). Тогда
$$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$$
поэтому
$$N(181)=(18+1)(36+1)=703=19\cdot 37.$$
То есть в этом примере вообще все сообщения оказываются unconcealed.
Для целевых простых подходящий оптимальный пример - \(e=11\). Эта экспонента допустима и удовлетворяет
$$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2,$$
откуда
$$N(11)=(2+1)(2+1)=9.$$
Значит, нижняя граница действительно достигается. Напротив, \(e=5\) тоже допустима, но
$$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$$
и потому \(N(5)=15\). Иными словами, минимизируется не сама экспонента, а два gcd-фактора.
Реализации на C++, Python и Java используют один и тот же короткий алгоритм. Сначала фиксируются два простых числа, затем вычисляется \(\varphi(n)=(p-1)(q-1)\), после чего перебираются все целые \(e\) в диапазоне \(2 \le e \lt \varphi(n)\).
Внутри цикла сначала проверяется RSA-условие \(\gcd(e,\varphi(n))=1\). Для каждого допустимого \(e\) программа напрямую вычисляет
$$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big),$$
сравнивает это значение с текущим лучшим и обновляет накопленную сумму экспонент, достигающих текущего минимума.
В реализации на C++ дополнительно присутствуют небольшие проверки корректности. Замкнутая формула сравнивается с прямым перебором через модульное возведение в степень на маленьких парах простых, а также отдельно подтверждается пример \(p=19\), \(q=37\), \(e=181\). Эти проверки не меняют основной алгоритм, а лишь подтверждают правильность формулы.
Внешний перебор рассматривает \(\varphi(n)-2\) кандидатов. Для каждого кандидата требуется лишь константное число вычислений gcd, а каждое такое вычисление занимает \(O(\log n)\) времени по алгоритму Евклида. Следовательно, полное время работы равно
$$O(\varphi(n)\log n).$$
Дополнительная память имеет порядок \(O(1)\), потому что хранятся только несколько целочисленных переменных. Это намного эффективнее, чем для каждого допустимого \(e\) проверять все \(n\) возможных сообщений.
نعمل هنا مع معامل RSA حيث \(n=pq\) وللقيمتين الأوليتين المحددتين \(p=1009\) و\(q=3643\). يكون الأس العام \(e\) صالحا إذا تحقق الشرطان
$$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$$
وتسمى الرسالة \(m\in\{0,1,\dots,n-1\}\) غير مخفية إذا لم يغيرها التشفير، أي إذا كان
$$m^e \equiv m \pmod n.$$
المطلوب هو إيجاد جميع الأسس الصالحة التي تجعل عدد الرسائل غير المخفية أصغر ما يمكن، ثم جمع هذه الأسس.
الفكرة الحاسمة هي أننا لا نحتاج إلى تجربة كل رسالة مع كل أس. عند تثبيت \(e\)، يمكن كتابة عدد النقاط الثابتة للدالة \(x\mapsto x^e \pmod n\) بصيغة مغلقة تعتمد فقط على قيمتي gcd.
لنبدأ بترديد عدد أولي \(r\)، حيث يكون \(r\) إما \(p\) أو \(q\). المعادلة
$$x^e \equiv x \pmod r$$
تكافئ
$$x(x^{e-1}-1)\equiv 0 \pmod r.$$
إذن كل حل إما أن يكون \(x=0\)، أو يكون عنصرا غير صفري يحقق \(x^{e-1}=1\). البواقي غير الصفرية بترديد \(r\) تشكل زمرة ضرب دورية رتبتها \(r-1\). وفي زمرة دورية رتبتها \(r-1\)، يكون عدد حلول المعادلة \(y^k=1\) مساويا تماما لـ \(\gcd(k,r-1)\). لذلك فإن عدد البواقي غير المخفية بترديد \(r\) هو
$$N_r(e)=\gcd(e-1,r-1)+1.$$
والحد \(+1\) يأتي من الحل \(x=0\).
يكون العدد غير مخفي بترديد \(n=pq\) إذا وفقط إذا كان غير مخفي بترديد \(p\) وبترديد \(q\) معا. وبما أن \(p\) و\(q\) أوليان مختلفان، فإن مبرهنة البواقي الصينية تعطي تقابلا واحدا لواحد بين أزواج البواقي بترديد \(p\) و\(q\) وبين البواقي بترديد \(n\). ومن ثم فإن العدد الكلي للرسائل غير المخفية يساوي
$$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$$
هذه هي الكمية المركزية في المسألة. بعد الوصول إليها، لم يعد المطلوب تعداد الرسائل، بل فهم كيف يمكن تصغير عاملي gcd قدر الإمكان.
بما أن \(p\) و\(q\) عددان أوليان فرديان، فإن \(p-1\) و\(q-1\) زوجيان، وبالتالي تكون \(\varphi(n)\) زوجية أيضا. وإذا كان \(\gcd(e,\varphi(n))=1\)، فلا بد أن يكون \(e\) فرديا، وهذا يعني أن \(e-1\) زوجي. لذلك نحصل دائما على
$$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$$
ومن هنا ينتج مباشرة
$$N(e)\ge (2+1)(2+1)=9.$$
إذن أصغر عدد ممكن للرسائل غير المخفية لأي أس صالح هو 9. ويتبقى أن نحدد متى يتحقق هذا الحد الأدنى فعلا مع القيمتين \(1009\) و\(3643\).
في بيانات المسألة نحصل على التحليلين
$$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$$
ولكي نصل إلى القيمة الدنيا 9، يجب أن تكون قيمتا gcd مساويتين تماما لـ 2. لذلك تكون الأسس المثلى هي بالضبط الأسس الصالحة \(e\) التي تحقق
$$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2.$$
وبصياغة أخرى، يجب أن يكون \(e-1\) زوجيا، لكن غير قابل للقسمة على أي من العوامل الأولية الفردية \(3\) أو \(7\) أو \(607\). هذه الصياغة أوضح بكثير من عد الرسائل مباشرة، ومع ذلك فهي نفس الكمية التي تحسبها التنفيذات لكل مرشح.
المثال المذكور في نص المسألة يستخدم \(p=19\) و\(q=37\) و\(e=181\). في هذه الحالة
$$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$$
ومن ثم
$$N(181)=(18+1)(36+1)=703=19\cdot 37.$$
أي أن كل الرسائل في هذا المثال تبقى غير مخفية.
أما بالنسبة إلى القيمتين المطلوبتين في المسألة، فإن \(e=11\) مثال بسيط على أس مثالي. فهو أس صالح، كما أن
$$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2,$$
ولذلك
$$N(11)=(2+1)(2+1)=9.$$
وهذا يثبت أن الحد الأدنى قابل للتحقيق. وعلى العكس من ذلك، فإن \(e=5\) صالح أيضا، لكن
$$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$$
فتكون النتيجة \(N(5)=15\). إذن ما يجري تصغيره ليس قيمة \(e\) نفسها، بل عاملا gcd.
تتبع تنفيذات C++ وPython وJava الخطة نفسها. فهي تثبت العددين الأوليين، وتحسب \(\varphi(n)=(p-1)(q-1)\)، ثم تمر على كل عدد صحيح \(e\) يحقق \(2 \le e \lt \varphi(n)\).
داخل هذه الحلقة يتم أولا فحص شرط الصلاحية في RSA، أي \(\gcd(e,\varphi(n))=1\). ولكل أس صالح، تحسب الشيفرة مباشرة
$$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big),$$
ثم تقارن هذه القيمة بأفضل قيمة شوهدت حتى تلك اللحظة، وتحدّث مجموع الأسس التي تحقق الحد الأدنى الحالي.
تنفيذ C++ يضيف أيضا بعض اختبارات السلامة الصغيرة. فهو يقارن الصيغة المغلقة مع عد مباشر يعتمد على الأس المعياري في أمثلة أولية صغيرة، كما يتحقق من مثال \(p=19\)، \(q=37\)، \(e=181\). هذه الاختبارات لا تغير الخوارزمية الأساسية، لكنها تؤكد صحة الصيغة قبل المسح النهائي.
المسح الخارجي يفحص \(\varphi(n)-2\) مرشحا. وكل مرشح يحتاج فقط إلى عدد ثابت من حسابات gcd، وكل حساب gcd يتم في \(O(\log n)\) باستخدام خوارزمية إقليدس. لذلك فإن الزمن الكلي يساوي
$$O(\varphi(n)\log n).$$
أما الذاكرة الإضافية فهي \(O(1)\)، لأن التنفيذ لا يحتاج إلا إلى عدد قليل من المتغيرات الصحيحة. وهذا أفضل بكثير من فحص كل الرسائل الممكنة لكل أس صالح.