Online diskret logaritme-løser

Hvad gør værktøjet?

Dette værktøj løser den diskrete logaritme for små tal. Det finder den mindste ikke-negative eksponent x, sådan at g^x ≡ h (mod p). For eksempel med standardværdierne g=2, h=8 og p=13, er resultatet x=3, fordi 2³ = 8 og 8 mod 13 = 8.

Eksempel med standardværdier

Indtast g=2, h=8, p=13. Værktøjet kontrollerer eksponenter fra 0 og opefter: 2⁰=1, 2¹=2, 2²=4, 2³=8. Da 8 mod 13 = 8, returneres x=3.

Sådan fungerer søgningen

Værktøjet starter med værdien 1 for eksponent 0 og opdaterer værdien som (værdi * g) mod p for hver efterfølgende eksponent. Det sammenligner h med den aktuelle værdi efter normalisering af h modulo p. Hvis ingen match findes efter p kontroller, rapporterer værktøjet, at der ikke er nogen løsning.

Begrænsninger

Modulus behøver ikke at være et primtal, og værktøjet beviser ikke, at g genererer en multiplikativ gruppe. Hvis g og p ikke er indbyrdes primiske, kan sekvensen gå i en kortere cyklus, men den udtømmende søgning finder stadig den første eksponent, hvis der findes en match. Søgningen er O(p) og er kun beregnet til undervisningsformål. Den er ikke en kryptografisk tjeneste og kan ikke håndtere store kryptografiske moduli.

Ofte stillede spørgsmål

Hvad sker der, hvis h er større end p?

Værktøjet normaliserer h modulo p, så hvis du indtaster h=21 og p=13, behandles det som h=8 (fordi 21 mod 13 = 8). Søgningen sammenligner derefter med den normaliserede værdi.

Kan jeg bruge negative værdier for h?

Ja, negative værdier normaliseres også modulo p. For eksempel, h=-5 med p=13 svarer til 8, fordi -5 mod 13 = 8.

Hvorfor er der en grænse på 1.000.000 for p?

Grænsen sikrer, at beregningen kører hurtigt i din browser uden at blokere siden. Større moduli ville kræve for lang tid til en udtømmende søgning.

Kontrol af resultatet

• Beregn g^x og tag modulus p for at verificere, at resultatet svarer til h.
• Husk, at værktøjet kun finder den mindste eksponent; der kan være flere løsninger, hvis g ikke er en generator.
• Brug værktøjet til undervisning og kontrol, ikke til sikkerhedsrelaterede formål.