27. april 2004 - 00:42Der er
8 kommentarer og 1 løsning
Valg af heltal x, hvor x skal opfylde gcd(x,a)=1, og a er kendt
Jeg har et problem i forbindelse med en hjemme-implementation af RSA. Det er under dannelsen af den offentlige nøgle.
Jeg har ledt og ledt, uden resultat, efter en metode til at vælge et lille (maks. 5 cifre), positivt og ulige heltal x, som opfylder gcd(x,a)=1, hvor a er et stort (i størrelsesordnen 600-700 cifre), positivt og lige heltal.
Findes der en metode, som kan konstruere et sådant tal, eller er man nødt til at prøve sig frem, indtil man rammer et, der passer?
Det virker som en overkommelig opgave at prøve sig frem. Når du ikke ved andet om a, end at det er lige, så undersøg blot primtal fra en ende af. hvis 3 ikke går op i a, er gcd(3,a)=1 hvis 5 ikke går op i a, er gcd(5,a)=1 ....
Ok, men så er det jo noget nemmere. Du har altså faktisk opløst dit store tal a i primfaktorer. Så vil ethvert primtal p forskellig fra 2 og forskellig fra dine primfaktorer have egenskaben gcd(p,a)=1. Du kan f.eks. vælge et primtal mindre end det mindste af dine primfaltorer.
Jeg har valgt at bruge erathostenes si til at finde en stribe primtal og så bare prøve dem indtil, der er et, som dur - altså den løsning du kom med nmh.
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
