🔢 mathematics

Symmetric measures of pseudorandomness for binary sequences

Dit artikel vergelijkt de gewone en symmetrische varianten van pseudorandomheidsmaten voor binaire sequenties, waarbij wordt aangetoond dat symmetrisering in zowel periodieke als aperiodieke contexten kan leiden tot aanzienlijk lagere complexiteitswaarden, met name voor niet-palindromische priemgetallen en specifieke families van eindige sequenties.

Oorspronkelijke auteurs: Yixin Ren, Arne Winterhof

Gepubliceerd 2026-03-25

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yixin Ren, Arne Winterhof

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Geheime Taal van Willekeur: Waarom het Spiegelen van Getallen Belangrijk is

Stel je voor dat je een zeer lange, willekeurige rij van nullen en enen hebt. Denk aan een reusachtige code die een computer gebruikt om je bankrekening te beschermen of je favoriete film te versleutelen. In de wereld van cryptografie noemen we zo'n rij een "binair sequence". Hoe goed is deze code? Dat hangt af van hoe moeilijk het is om de code te kraken.

Wetenschappers gebruiken twee speciale meetlatjes om deze moeilijkheidsgraad te bepalen:

De Lineariteit: Hoe simpel is het om de volgende cijfers te voorspellen als je een patroon ziet? (Alsof je een machine bouwt die de rij na-ijlt).
De 2-adische Complexiteit: Een iets ingewikkelder maatstaf die kijkt naar hoe de getallen zich gedragen als je ze in een heel specifiek wiskundig systeem (de "2-adische getallen") bekijkt.

Het Grote Geheim: De Spiegel

In dit artikel kijken Yixin Ren en Arne Winterhof naar een nieuw fenomeen: wat gebeurt er als je de code niet alleen van links naar rechts leest, maar ook van rechts naar links?

Stel je een rij getallen voor als een lange trein.

De gewone maatstaf kijkt alleen naar de trein die vooruit rijdt.
De symmetrische maatstaf kijkt naar zowel de trein die vooruit rijdt, als de trein die achteruit rijdt (de spiegelbeeld). De "veiligheid" van de code wordt dan bepaald door de zwakste van de twee. Als de trein vooruit heel sterk is, maar de trein achteruit heel makkelijk te kraken is, dan is de hele code eigenlijk zwak.

Wat hebben ze ontdekt?

De auteurs hebben twee belangrijke situaties onderzocht:

1. De Periode (De Trein die in een Rondje rijdt)
Soms rijdt de trein in een oneindig rondje (een periodieke rij).

Verrassing 1: Ze ontdekten dat voor bepaalde speciale getallen (die "niet-palindromische priemgetallen" heten), de trein die achteruit rijdt veel makkelijker te kraken is dan de trein die vooruit rijdt. Het spiegelbeeld is dus een zwakke schakel.
Verrassing 2: Maar! Voor de "lineariteit" (de eerste meetlat) bleek dat het spiegelbeeld precies even sterk is als het origineel. Of je de trein nu vooruit of achteruit laat rijden, de moeilijkheidsgraad is hetzelfde. Dit is een bewezen feit dat ze met een korte, elegante redenering hebben bevestigd.

2. De Aperiodische Situatie (De Trein die stopt)
In de echte wereld stoppen codes vaak (ze zijn eindig, geen oneindige rondjes). Hier wordt het echt interessant.

Het Grote Verschil: Ze vonden families van codes waarbij het spiegelbeeld veel makkelijker te kraken is dan het origineel. Het verschil is niet klein; het is enorm.
De Verwachting: Als je willekeurige codes neemt, blijkt dat de gemiddelde veiligheid van het spiegelbeeld aanzienlijk lager is dan die van het origineel. Het verschil groeit exponentieel. Stel je voor dat de originele code een betonnen muur is, en het spiegelbeeld slechts een papieren scherm. Als je alleen naar de papieren schermen kijkt (de symmetrische maatstaf), lijkt de hele wereld veel kwetsbaarder dan wanneer je alleen naar de betonnen muren kijkt.

Waarom is dit belangrijk?

Stel je voor dat je een slot op je deur hebt.

De gewone maatstaf zegt: "Dit slot is superveilig, niemand kan het openen."
De symmetrische maatstaf zegt: "Wacht even, als je het slot van de andere kant bekijkt (of als je de sleutelholte spiegelt), is het eigenlijk heel makkelijk te openen."

De auteurs tonen aan dat we in de cryptografie niet alleen moeten kijken naar hoe sterk een code is, maar ook naar hoe sterk hij is als je hem "omdraait". Voor sommige codes maakt dit een enorm verschil. Als je een systeem ontwerpt dat willekeurige codes gebruikt, moet je oppassen dat je niet per ongeluk een zwakke spiegelbeeld creëert.

Samenvattend in één zin:
Deze wetenschappers hebben laten zien dat het "spiegelen" van een willekeurige getallenrij de veiligheid van die rij soms drastisch kan verlagen, en dat we dit effect goed moeten begrijpen om veilige digitale systemen te bouwen.

Titel: Symmetrische maatstaven voor pseudorandomiteit van binaire sequenties

Auteurs: Yixin Ren (Noordwest-Universiteit, China) en Arne Winterhof (Johann Radon Instituut, Oostenrijk).

1. Probleemstelling en Achtergrond

Maatstaven voor pseudorandomiteit zijn cruciaal voor de analyse en het ontwerp van stroomchiffers. Twee van de belangrijkste complexiteitsmaatstaven voor binaire sequenties zijn:

Lineaire complexiteit: De lengte van de kortste lineaire terugkoppelschuifregister (LFSR) dat een gegeven sequentie genereert.
2-adische complexiteit: Gerelateerd aan de lengte van een feedback-with-carry schuifregister (FCSR) en de 2-adische expansie van rationale getallen.

Tot nu toe is de meeste theorie ontwikkeld voor de "gewone" (ordinale) complexiteit. In recente jaren zijn echter symmetrische varianten onderzocht, waarbij de complexiteit wordt geminimaliseerd over een sequentie $S$ en zijn omgekeerde $S^{rev}$ . Hoewel dit voor specifieke periodieke families is bestudeerd, ontbreekt er een systematische vergelijking tussen gewone en symmetrische maatstaven, met name in de aperiodische context (eindige sequenties).

Het doel van dit papier is om deze kloof te dichten door een vergelijking te maken voor zowel de 2-adische als de lineaire complexiteit in periodieke en aperiodieke settings.

2. Methodologie

De auteurs analyseren binaire sequenties $S = (s_n)$ en hun reverses $S^{rev}$ . Ze definiëren de symmetrische complexiteit als:
$\text{Complexiteit}_{sym}(S) = \min(\text{Complexiteit}(S), \text{Complexiteit}(S^{rev}))$

De analyse is verdeeld in twee hoofdsecties:

Periodieke setting: Sequenties met periode $T$ . De auteurs gebruiken getaltheoretische eigenschappen van priemgetallen en hun binaire expansies.
Aperiodieke setting: Eindige sequenties van lengte $N$ . Hier worden verwachtingswaarden (expected values) berekend over de ruimte van alle $2^N$ mogelijke binaire sequenties. Ze gebruiken combinatorische tellingen en asymptotische analyse om onder- en bovengrenzen te bepalen.

3. Belangrijkste Bijdragen en Resultaten

A. Periodieke Setting

2-adische complexiteit:
- De auteurs tonen aan dat voor binaire periodieke sequenties, afgeleid van niet-palindromische priemgetallen, de symmetrische 2-adische complexiteit strikt kleiner kan zijn dan de gewone 2-adische complexiteit.
- Stelling 1: Als $p$ een niet-palindromisch priemgetal is en $q$ het omgekeerde getal, dan kan een sequentie worden geconstrueerd waarbij $\lambda(S) = \log_2(2^T - 1)$ maar $\lambda_{sym}(S) = \lambda(S) - \log_2(q)$ . Dit betekent dat symmetrische maatstaven zwaktes in sequenties kunnen blootleggen die door de gewone maatstaf worden gemist.
- Er worden lijsten gegeven van omkeerbare priemparen $(p, q)$ en hun orden modulo 2.
Lineaire complexiteit:
- Propositie 1: De auteurs geven een directe bewijsvoering (gebaseerd op de recursieve definitie) dat de lineaire complexiteit van een periodieke sequentie invariant is onder reversie: $L(S) = L(S^{rev})$ .
- Conclusie: In de periodieke setting is de symmetrische lineaire complexiteit identiek aan de gewone lineaire complexiteit. Er is dus geen winst te behalen door symmetrisering voor periodieke sequenties wat betreft lineaire complexiteit.

B. Aperiodieke Setting (Eindige Sequenties)

In tegenstelling tot de periodieke setting, tonen de auteurs aan dat symmetrisering hier een significant effect heeft.

Families met lage complexiteit:
- Er worden expliciete families van eindige binaire sequenties geconstrueerd waarbij zowel de $N$ -de symmetrische 2-adische complexiteit als de symmetrische lineaire complexiteit substantieel kleiner zijn dan hun gewone tegenhangers.
- Voorbeelden worden gegeven van sequenties met veel nullen of veel enen aan het begin, wat leidt tot een lage complexiteit bij reversie.
Verwachtingswaarden (Expected Values):
- Rationale en 2-adische complexiteit: De verwachte waarde van de $N$ -de rationale complexiteit ( $E_{rat}$ ) en 2-adische complexiteit ( $E_{2-adic}$ ) overschrijdt die van hun symmetrische analogen ( $E_{rat-sym}$ en $E_{2-adic-sym}$ ) met een term van de orde $N$ .
- Propositie 2: $E_{rat-sym} \leq E_{rat} - \frac{3N}{8} + O(1)$ .
- Exponentiële lineaire complexiteit: De verwachte waarde van $2^{L(S)}$ (exponentiële lineaire complexiteit) is aanzienlijk hoger dan die van de symmetrische versie.
- Propositie 3: $E_{lin-exp-sym} \leq E_{lin-exp} - \frac{3N}{4} + O(1)$ .
- Dit impliceert dat het effect van symmetrisering zichtbaar is op een exponentiële schaal.
Ondergrenzen:
- Stelling 2 en 3: De auteurs stellen ondergrenzen vast voor de verwachte waarden van de symmetrische complexiteiten.
  - $E_{rat-sym} \geq 2^{N/2 - r(N)}$
  - $E_{2-adic-sym} \geq \frac{N}{2} - \log(N)$
  - $E_{lin-sym} \geq \frac{N}{2} - \log(N)$
- Hoewel deze ondergrenzen lager zijn dan die voor de gewone complexiteit, blijven ze significant hoog, wat aangeeft dat de meeste sequenties toch nog een hoge symmetrische complexiteit behouden.

4. Significatie en Conclusie

De belangrijkste bevindingen van dit onderzoek zijn:

Periodieke vs. Aperiodieke: In de periodieke setting is de symmetrische lineaire complexiteit gelijk aan de gewone, maar de symmetrische 2-adische complexiteit kan lager zijn. In de aperiodieke setting (eindige sequenties) is het verschil echter overal significant.
Zichtbaarheid op Exponentiële Schaal: Het verschil tussen gewone en symmetrische complexiteit is niet triviaal; het is van de orde $N$ in de verwachte waarde, wat resulteert in een groot verschil op de schaal van $2^N$ . Dit betekent dat symmetrische maatstaven een veel strengere test voor pseudorandomiteit kunnen zijn.
Veiligheid van Stroomchiffers: Voor het ontwerp van cryptografische systemen is het cruciaal om niet alleen de gewone complexiteit te controleren, maar ook de symmetrische variant, vooral voor eindige blokken data. Een sequentie die veilig lijkt volgens de gewone maatstaf, kan kwetsbaar zijn als zijn reversie een lage complexiteit heeft.

Samenvattend vullen de auteurs de theoretische kennis aan door te tonen dat symmetrisering een krachtig hulpmiddel is om zwaktes in binaire sequenties te detecteren die door traditionele maatstaven worden over het hoofd gezien, met name in aperiodieke contexten.