Period of the power generator and small values of Carmichael’s function
Pourquoi ce travail est-il dans la base ?
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Prédiction distillée sur la base complète
Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
- Catégories candidates
- aucune
- Catégories consensuelles
- aucune
- Domaine
- Signal candidat: aucuneSignal consensuel: aucune
- Devis d'étude
- Signal candidat: Simulation ou modélisationSignal consensuel: aucune
- Genre
- Signal candidat: EmpiriqueSignal consensuel: Empirique
- Score de désaccord entre enseignants
- 0,704
- Score d'incertitude au seuil
- 0,664
- Statut de validation
machine_predicted_unvalidated·codex-gemma-dda1882f352a
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,001 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,000 |
| Études des sciences et des technologies | 0,000 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,000 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
- Écart entre enseignants
- 0,211 · la distance entre les deux têtes enseignantes sur ce seul travail
- Statut de validation
score_only:v0-immature-baseline· tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découle
Résumé
Consider the pseudorandom number generator<disp-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u Subscript n Baseline identical-to u Subscript n minus 1 Superscript e Baseline left-parenthesis mod m right-parenthesis comma 0 less-than-or-equal-to u Subscript n Baseline less-than-or-equal-to m minus 1 comma n equals 1 comma 2 comma ellipsis comma"><mml:semantics><mml:mrow><mml:msub><mml:mi>u</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>≡</mml:mo><mml:msubsup><mml:mi>u</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>e</mml:mi></mml:msubsup><mml:mspace width="0.667em"/><mml:mo stretchy="false">(</mml:mo><mml:mi>mod</mml:mi><mml:mspace width="0.333em"/><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mspace width="1em"/><mml:mn>0</mml:mn><mml:mo>≤</mml:mo><mml:msub><mml:mi>u</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>≤</mml:mo><mml:mi>m</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mspace width="1em"/><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\begin{equation*} u_n\equiv u_{n-1}^e\pmod {m},\quad 0\le u_n\le m-1,\quad n=1,2,\ldots , \end{equation*}</mml:annotation></mml:semantics></mml:math></disp-formula>where we are given the modulus<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>, the initial value<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u 0 equals theta"><mml:semantics><mml:mrow><mml:msub><mml:mi>u</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>ϑ</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">u_0=\vartheta</mml:annotation></mml:semantics></mml:math></inline-formula>and the exponent<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="e"><mml:semantics><mml:mi>e</mml:mi><mml:annotation encoding="application/x-tex">e</mml:annotation></mml:semantics></mml:math></inline-formula>. One case of particular interest is when the modulus<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>is of the form<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p l"><mml:semantics><mml:mrow><mml:mi>p</mml:mi><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">pl</mml:annotation></mml:semantics></mml:math></inline-formula>, where<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p comma l"><mml:semantics><mml:mrow><mml:mi>p</mml:mi><mml:mo>,</mml:mo><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">p,l</mml:annotation></mml:semantics></mml:math></inline-formula>are different primes of the same magnitude. It is known from work of the first and third authors that for moduli<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m equals p l"><mml:semantics><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mi>p</mml:mi><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">m=pl</mml:annotation></mml:semantics></mml:math></inline-formula>, if the period of the sequence<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis u Subscript n Baseline right-parenthesis"><mml:semantics><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>u</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">(u_n)</mml:annotation></mml:semantics></mml:math></inline-formula>exceeds<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m Superscript 3 slash 4 plus epsilon"><mml:semantics><mml:msup><mml:mi>m</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>3</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>4</mml:mn><mml:mo>+</mml:mo><mml:mi>ε</mml:mi></mml:mrow></mml:msup><mml:annotation encoding="application/x-tex">m^{3/4+\varepsilon }</mml:annotation></mml:semantics></mml:math></inline-formula>, then the sequence is uniformly distributed. We show rigorously that for almost all choices of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p comma l"><mml:semantics><mml:mrow><mml:mi>p</mml:mi><mml:mo>,</mml:mo><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">p,l</mml:annotation></mml:semantics></mml:math></inline-formula>it is the case that for almost all choices of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="theta comma e"><mml:semantics><mml:mrow><mml:mi>ϑ</mml:mi><mml:mo>,</mml:mo><mml:mi>e</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">\vartheta ,e</mml:annotation></mml:semantics></mml:math></inline-formula>, the period of the power generator exceeds<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis p l right-parenthesis Superscript 1 minus epsilon"><mml:semantics><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>p</mml:mi><mml:mi>l</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mi>ε</mml:mi></mml:mrow></mml:msup></mml:mrow><mml:annotation encoding="application/x-tex">(pl)^{1-\varepsilon }</mml:annotation></mml:semantics></mml:math></inline-formula>. And so, in this case, the power generator is uniformly distributed. We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto. The principal tool is an estimate related to the Carmichael function<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda left-parenthesis m right-parenthesis"><mml:semantics><mml:mrow><mml:mi>λ</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\lambda (m)</mml:annotation></mml:semantics></mml:math></inline-formula>, the size of the largest cyclic subgroup of the multiplicative group of residues modulo<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>. In particular, we show that for any<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Delta greater-than-or-equal-to left-parenthesis log log upper N right-parenthesis cubed"><mml:semantics><mml:mrow><mml:mi mathvariant="normal">Δ</mml:mi><mml:mo>≥</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mi>N</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mn>3</mml:mn></mml:msup></mml:mrow><mml:annotation encoding="application/x-tex">\Delta \ge (\log \log N)^3</mml:annotation></mml:semantics></mml:math></inline-formula>, we have<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda left-parenthesis m right-parenthesis greater-than-or-equal-to upper N exp left-parenthesis negative normal upper Delta right-parenthesis"><mml:semantics><mml:mrow><mml:mi>λ</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>≥</mml:mo><mml:mi>N</mml:mi><mml:mi>exp</mml:mi><mml:mo></mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo>−</mml:mo><mml:mi mathvariant="normal">Δ</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\lambda (m)\ge N\exp (-\Delta )</mml:annotation></mml:semantics></mml:math></inline-formula>for all integers<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>with<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 less-than-or-equal-to m less-than-or-equal-to upper N"><mml:semantics><mml:mrow><mml:mn>1</mml:mn><mml:mo>≤</mml:mo><mml:mi>m</mml:mi><mml:mo>≤</mml:mo><mml:mi>N</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">1\le m\le N</mml:annotation></mml:semantics></mml:math></inline-formula>, apart from at most<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N exp left-parenthesis minus 0.69 left-parenthesis normal upper Delta log normal upper Delta right-parenthesis Superscript 1 slash 3 Baseline right-parenthesis"><mml:semantics><mml:mrow><mml:mi>N</mml:mi><mml:mi>exp</mml:mi><mml:mo></mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mo>−</mml:mo><mml:mn>0.69</mml:mn><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi mathvariant="normal">Δ</mml:mi><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mi mathvariant="normal">Δ</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
La notice
- Revue
- Mathematics of Computation
- Thématique
- Chaos-based Image/Signal Encryption
- Domaine
- Computer Science
- Établissements canadiens
- University of Toronto
- Organismes subventionnaires
- Natural Sciences and Engineering Research Council of Canada
- Mots-clés
- AlgorithmMaterials scienceComputer science
- Résumé présent dans OpenAlex
- oui