Efficient Jump Ahead for 𝔽<sub>2</sub>-Linear Random Number Generators

2008· article· en· 79 citations· W2123577276 sur OpenAlex· 10.1287/ijoc.1070.0251

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.

Affiliation canadienneUne personne signataire a déclaré un établissement canadien. C'est la seule voie dont dispose la base habituelle.

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: Méta-épidémiologie (sens strict)
Catégories consensuelles: aucune
Domaine: Signal candidat: aucuneSignal consensuel: aucune
Devis d'étude: Signal candidat: Simulation ou modélisationSignal consensuel: Simulation ou modélisation
Genre: Signal candidat: EmpiriqueSignal consensuel: aucune
Score de désaccord entre enseignants: 0,446
Score d'incertitude au seuil: 1,000
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,001
Études des sciences et des technologies	0,001	0,000
Communication savante	0,000	0,000
Science ouverte	0,001	0,000
Intégrité de la recherche	0,000	0,001
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.

Tête enseignante Opus0,021

Tête enseignante GPT0,261

Écart entre enseignants: 0,240 · 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é

The fastest long-period random number generators currently available are based on linear recurrences modulo 2. So far, software that provides multiple disjoint streams and substreams has not been available for these generators because of the lack of efficient jump-ahead facilities. In principle, it suffices to multiply the state (a k-bit vector) by an appropriate k × k binary matrix to find the new state far ahead in the sequence. However, when k is large (e.g., for a generator such as the popular Mersenne twister, for which k = 19,937), this matrix-vector multiplication is slow, and a large amount of memory is required to store the k × k matrix. In this paper, we provide a faster algorithm to jump ahead by a large number of steps in a linear recurrence modulo 2. The method uses much less than the k 2 bits of memory required by the matrix method. It is based on polynomial calculus modulo the characteristic polynomial of the recurrence, and uses a sliding window algorithm for the multiplication.

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: INFORMS journal on computing
Thématique: Chaos-based Image/Signal Encryption
Domaine: Computer Science
Établissements canadiens: Université de Montréal
Organismes subventionnaires: Japan Society for the Promotion of Science
Mots-clés: ModuloMathematicsMatrix multiplicationPseudorandom number generatorJumpTime complexityDisjoint setsDiscrete mathematicsRandom number generationMatrix (chemical analysis)Multiplication (music)Sequence (biology)State (computer science)CombinatoricsAlgorithmIterated function
Résumé présent dans OpenAlex: oui
API: /api/v1/works/W2123577276