SYSTEMY SZYFROWANIA Z KLUCZEM JAWNYM 
 
Konwencjonalnie – szyfrowanie i deszyfrowanie  to ten sam  klucz(hasło) 
Można  inaczej    szyfrowanie-- pierwszy klucz(A), deszyfrowanie  inny 
B=B(A) 
Co to daje    
1.

 

Nie można „obliczyć” klucza deszyfrującego znając jedynie klucz A i 
algorytm szyfrujący 

2.

 

Są algorytmy, dla których każdy ze związanych ze sobą kluczy A i B można 
użyć do szyfrowanie i deszyfrowania 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1.

 

SYSTEMY KOŃCOWE GENERUJĄ PARĘ KLUCZY DO 
SZYFROWANIA I DESZYFROWANIA 

2.

 

KAŻDY SYSTEM UDOSTĘPNIA, PUBLIKUJE SWÓJ KLUCZ 
SZYFRUJĄCY, JEST TO KLUCZ JAWNY. DRUGI KLUCZ JEST 
PRYWATNY 

3.

 

JEŻELI A WSYLA TO SZYFRUJE DANE KLUCZEM JAWNYM 
ODBIORCY B 

4.

 

ODBIORCA B DESZYFRUJE DANE ZA POMOCĄ SWEGO KLUCZA 
PRYWATNEGO. TYLKO ON MOŻE TO WYKONAĆ. 

Taki sposób posługiwania się kluczami zapewnia poufność.  Kryptoanalityk  
musi wygenerować bardzo wiele hipotetycznych kluczy prywatnych B  aby 
rozszyfrować dane. 
Jeśli użyjemy algorytmu umożliwiającego przestawianie kluczy to możemy 
zrealizować funkcję uwierzytelnienia.  A  swój komunikat szyfruje go za 
pomocą swego klucza prywatnego i przesyła go do B, ten zaś odszyfrowuje go 

Algorytm 
szyfrujący 

Algorytm  
deszyfrujący 

Tekst  
zaszyfrowany 

Tekst 
jawny 

Tekst 
jawny 

Użytkownik A 

Użytkownik B 

Klucz jawny B 

Klucz prywatny 
B 

za pomocą klucza jawnego pochodzącego od A. Odbiorca B ma pewność, że 
tylko A mógł wysłać komunikat.  Nikt po drodze nie może przechwycić 
komunikatu w celu   jego podmiany bo nie zna klucza prywatnego nadawcy A. 
Ale każdy, kto ma dostęp do bazy z kluczem publicznym nadawcy A może 
łatwo odszyfrować tekst czyli nie jest to poufne. 
  Należy zastosować podwójne szyfrowanie 
1

 

Nadawca szyfruje komunikat za pomocą swojego klucza prywatnego. 

2

 

Nadawca szyfruje otrzymany wynik drugi raz za pomocą klucza jawnego 
odbiorcy 

3

 

Otrzymane  dane   może odszyfrować tylko B swoim kluczem prywatnym 
czyli jest zapewniona poufność bo wiadomość jest tylko dla niego. 

4

 

Jawny tekst otrzyma stosując klucz publiczny nadawcy. 

Ale aż 4 razy trzeba stosować algorytm szyfrowania. 
 
Wymagania dla algorytmów szyfrująco / deszyfrujących z wykorzystaniem 
kluczy prywatnych i publicznych są wysokie. Na dziś powszechnie 
akceptowalny jest algorytm RSA (system Rivesta-Shamira-Adlemana) 
 

 

******************************************************************* 
 
Przedstawione poniżej algorytmy szyfrowania danych są szyframi blokowymi.

  

Omówione zostaną:

  

1)z grupy szyfrów wykładniczych szyfr Pohliga-Hallmana

  

2)z grupy szyfrów wykładniczych szyfr RSA(Rivest-Shamir-Adleman)

  

W grupie szyfrów wykładniczych i plecakowych w celu zrozumienia zasad 
szyfrowania i ewentualnej próby złamania szyfru należy wprowadzić niezbędne 
definicje i twierdzenia z zakresu teorii liczb.

  

Wstęp do arytmetyka modularnej:  
Definicja1:  
Dwie liczby całkowite a i b przystają do siebie według modułu n tzn.  
a

≡

nb ,

  

gdzie n jest liczbą całkowitą różną od 0 wtedy i tylko wtedy, gdy istnieje  
liczba całkowita k, dla której:  
a-b = kn.  
Np. 17

≡

5

7, ponieważ 17-7 =2*5.   tą liczbą k  jest 2 

Wówczas dla a

≡≡≡≡

nb

, b jest nazywane residuum a modulo n.  

Definicja2:  
Zbiór liczb całkowitych (r

1,...,rn

) nazywamy zbiorem zupełnym residuów modulo 

n, jeśli dla każdej liczby całkowitej a istnieje w tym zbiorze dokładnie jeden 

element

 r

i

, 

dla którego zachodzi

 

a

 

≡

n

ri

  

Można zauważyć, że dla dowolnego modulo n zbiór liczb (0,1,....,n-1) stanowi 
zbiór zupełny residuów modulo n.

  

W arytmetyce modularnej liczb całkowitych modulo n obowiązują te same prawa 
łączności, rozdzielności i przemienności działań co w arytmetyce liczb 
całkowitych.

 

 

Twierdzenie1

  

Niech a1 i a2 będą liczbami całkowitymi ,zaś op  jest operatorem: +,-, lub *. 
Wtedy:

  

(a1 op a2) mod n= [(a1 mod n) op (a2 mod n)] mod n.  

 
Czyli prawdziwe są działania:

  

 
(a1 +a2) mod n=[(a1 mod n) +(a2 mod n)] mod n  
i  
(a1*a2) mod n=[(a1 mod n) * (a2 mod n)] mod n  

oraz co najważniejsze możliwe jest skuteczne potęgowanie to znaczy że:

  

∏

−

=

t

i

t

n

n

e

n

e

1

mod

)]

mod

(

[

mod

 

gdzie 0 

≤

 

t 

≤

 n-1

  

Kolejne mnożenia modulo n zmniejszają wielkość pośrednich wyników. W 
praktyce dla k-bitowej liczby n to znaczy takiej ze 2

k-1

 

≤

n < 2

k 

wynik 

odejmowania, dodawania lub mnożenia nie przekroczy długości 2k bitów. To 
oznacza wykonywanie operacji potęgowania modulo n bez konieczności 
rezerwowania zbyt dużej pamięci na wyniki pośrednie.  

Dowód twierdzenia 1:

  

niech a1=k1*n+r1 oraz a2=k2*n+r2 wtedy:

  

 

(a1+ a2) mod n= [(k1*n+r1)+(k2*n+r2)] mod n=

  

 

[((k1+k2)*n +(r1+r2)]mod n= (r1+r2) mod n=

  

[(a1 mod n)+(a2 mod n)] mod n.

  

 

Poniżej podano przykładową funkcję w C szybkiego potęgowania liczb mod n

  

 
long int fastexp(long a, long z, long n)

  

{

  

 long z1=z;

  

 long x=1;

  

 long a1=a;

  

 while (z1)

  

{

  

 while(!(z1%2))

  

 {

  

  z1=(int)(z1/2);

  

  a1=((int)(a1*a1)) % n;

  

 }

  

 z1-=1;

  

 x=((int)(x*a1)) % n;

  

}

  

return(x);

  

}

  

 

Bardzo ważnym zagadnieniem w arytmetyce modularnej jest obliczanie 
odwrotności iloczynowych modulo n. Np. liczby 3 i 7 są odwrotnościami mod 
10 ponieważ:  

3*7 mod 10 =1  
   
   
Twierdzenie 2  

Można dowieść że dla równania : ax mod n = 1 jeśli tylko gcd(a,n)=1 (greatest 
common divisor) to znaczy: że liczby a i n są liczbami wzajemnie pierwszymi, to 
istnieje pewna liczba 0< x < n, która jest odwrotnością liczby a modulo n.

  

Twierdzenie powyższe jedynie stwierdza możliwość istnienia odwrotności liczby, 
ale nie określa sposobu wyliczenia tejże odwrotności. W tym celu wprowadźmy 
pewne dodatkowe definicje:

  

Definicja3:

  

Zbiorem zredukowanym residuów mod n nazywamy podzbiór residuów {0,1,...,n-
1} względnie pierwszych z n

  

Na przykład zbiorem zredukowanym residuów mod 10 jest zbiór {1,3,7,9}

  

Uwaga do definicji 3:

  

Jeśli n jest liczbą pierwszą, to zredukowany zbiór jest równoważny zbiorowi 
zupełnemu residuów o elementach {1,...,n-1}, z wyłączeniem zera!

  

Definicja4:

  

Funkcja Eulera 

Φ

(n) 

określa liczbę elementów w zredukowanym zbiorze 

residuów modulo n, czyli

 

Φ(

n) jest liczbą całkowitych liczb dodatnich mniejszych 

od n i względnie pierwszych z n.

  

Na przykład 

Φ(10) = 4, 

a 

Φ(11) = 10,

 czyli funkcja Eulera dla n=11 wynosi n-1, 

ponieważ wszystkie elementy zbioru residuum zupełnego są względnie pierwsze 
względem 11.

  

Twierdzenie 3

  

Dla pewnej liczby n będącej iloczynem liczb pierwszych p i q zachodzi zależność: 

Φ(

n

)

 =

 Φ(

p

)

 * 

Φ(

q

)

 =(p-1) *(q-1)

  

Na przykład: 

φ(21)

 = 

φ(7)

 * 

φ(3)

 = (7-1)*(3-1) =12, czyli występuje 12 elementów 

w granicach {1,...,21-1} względnie pierwszych z 21.

  

  

Twierdzenie4

  

Niech dana będzie liczba pierwsza p, wtedy dla każdej liczby a względnie 
pierwszej z p tj. gcd(a,p)=1 zachodzi równość:

  

a 

p-1

mod p =1

  

Z uogólnienia Eulera wynika, że rozwiązanie równości:

  

ax mod n =1 ma postać:

  

x=a

 

Φ

(n)-1

 mod n  

Uwaga do rozwiązania powyższej równości:

  

Je

ś

li liczba n jest liczb

ą

 pierwsz

ą

 to obliczenie odwrotno

ś

ci liczby a upraszcza si

ę

  

do postaci:

  

x=a

n-2

 mod n

  

Przykład:

  

dla a=3, n=7, czyli dla równania:    3x mod 7=1 otrzymujemy rozwiązanie:

  

x=3

5

 mod 7 co równa się 5

  

ponieważ: 3*5 mod 7 =1.

  

Uwaga:

  

Do obliczania odwrotności x w stosunku do liczby a modulo n, jeśli tylko znana 
jest wartość funkcji Eulera 

Φ

(n), można się posłużyć przytoczoną powyżej funkcją 

szybkiego potęgowania, fastexp(a,z,n), która zwraca wartość określoną wzorem:

  

a

z

 mod n

  

Inny sposób obliczania odwrotności x liczby a modulo n polega zastosowaniu 
rozszerzonego algorytmu Euklidesa do obliczania gcd(największego wspólnego 
podzielnika). W przykładzie  podano funkcję liczącą według algorytmu 
Euklidesa gcd dwóch liczb całkowitych a i n.  

 
long gcd(long a, long n)

  

{

  

 long g0=n;

  

 long g1=a;

  

 long g2;

  

 long i=1;

  

while(g1)

  

{

  

 g2=g0 % g1;

  

 g0=g1;

  

 g1=g2;

  

 i++;

  

}

  

return(g0);

  

}

  

 
Do obliczania odwrotności liczby a modulo n przydałby się rozszerzony algorytm 
Euklidesa:

  

Program nr.3

  

#include<stdio.h>

  

#include<stdlib.h>

  

#include<conio.h>

  

long inv(long a, long n)

  

{

  

long g0=n;

  

long g1=a;

  

long g2;

  

long u0=1;

  

long u1=0;

  

long u2;

  

long v0=0;

  

long v1=1;

  

long v2;

  

long i=1;

  

long y;

  

while(g1)

  

{

  

 y=(int)(g0/g1);

  

 g2=g0-(int)(y*g1);

  

 u2=u0-(int)(y*u1);

  

 v2=v0-(int)(y*v1);

  

 g0=g1;

  

 g1=g2;

  

 u0=u1;

  

 u1=u2;

  

 v0=v1;

  

 v1=v2;

  

 i++;

  

}

  

if(v0>=0)

  

 return(v0);

  

else

  

 return(v0+n);

  

}

  

 
Przeciętna liczba dzieleń wykonywanych w tym algorytmie została oszacowana 
przez Knutha na około (0,843 ln n + 1,47).

  

Oczywiście omawiany algorytm można rozszerzyć, w celu obliczania liczby x z 
bardziej ogólnego równania:

  

ax mod n =b , gdzie a i n spełniają równanie gcd(a,n)=1

  

W tym celu:  

1)należy obliczyć x

o 

z równania   

axo mod n = 1  

2)po przekształceniu tego powyższego równania otrzymamy:

  

abx

o

 mod n =1 skąd :  

x=bx

o

 mod n  

Do obliczenia liczby x może posłużyć zdefiniowane wcześniej funkcje w postaci 
wyrażenia dla nieznanej funkcji Eulera:  
x=(b*inv(a,n)) mod n  
lub też dla znanej funkcji Eulera:  
x=(b*fastexp(a, 

Φ

(n) -1,n)) mod n  

Szyfry potęgowe:

  

 

Obydwa szyfry pot

ę

gowe, które zostan

ą

 tutaj omówione realizuj

ą

 szyfrowanie 

bloku tekstu jawnego M od długo

ś

ci co najmniej 200 bitów.  

1)

Szyfr Pohliga-Hallmana realizuje szyfrowanie w następujący sposób:

  

(1) C=M

e

mod n, gdzie:  

 

M (message)- oznacza tekst jawny  
C - oznacza tekst zaszyfrowany  
e - pewien wykładnik wynikający z uogólnienia Eulera  
n - pewna duża liczba, której wybór zależy od metody szyfrowania 
wykładniczego.  

Uwaga:

  

M musi należeć do przedziału [0,...,n-1] , stąd też po długości bloków tekstu 
poddawanego szyfrowaniu można w przybliżeniu określić wielkość liczby n.

  

Deszyfracja polega na wykonaniu następującej operacji:

  

 

(2) M=C

d

mod n, 

gdzie:

  

d - to pewien wykładnik wynikający z uogólnienia Eulera

  

Z uogólnienia Eulera twierdzenia Fermata wynika, że dla każdej liczby M 
względnie pierwszej z n      M

Φ

Φ

Φ

Φ

(n)mod n = 

1     zachodzi zależność:  

   

(3)   ed mod 

Φ

Φ

Φ

Φ

(n) =1  

 
Można udowodnić, ze dla e i d spełniających zależność (3) równania (1) i (2) 
realizują operacje wzajemnie odwrotne.

  

Twierdzenie5:  

Dla danych e i d spełniających równanie (3) oraz wiadomości M zawierającej 
się w przedziale [0,..,n-1] oraz względnie pierwszej z n to znaczy: gcd(M,n)=1

  

 
(4)   (M

e

mod n)

d

 mod n=M  

 
Znając wartość funkcji Eulera 

Φ

(n) dla danej liczby n, z łatwością można 

wygenerować parę liczb e i d . W tym celu dokonuje się wyboru liczby d względnie 
pierwszej z 

Φ

(n) po czym zgodnie z zależnością (3) dokonuje się wyliczenia 

odwrotności e liczby d modulo 

Φ

(n), na przykład korzystając z algorytmu 

rozszerzonego Euklidesa:

  

e=inv(d,

Φ

(n)).

  

Uwagi co do łamalności przedstawionego szyfru wykładniczego:

  

Mając d łatwo można obliczyć e mając 

Φ

(n).

 Tajemnicę szyfru można więc ukryć 

zachowując w tajemnicy 

Φ

(n) i d, liczby potrzebne do deszyfracji, podczas gdy e 

wykładnik potrzebny do szyfracji tekstu może być powszechnie znany.

  

Ewentualnie zachowując e i d, czyli szyfr ten może posłużyć jedynie do 
klasycznego szyfrowania    (

bez klucza jawnego

)  

Przykład:

  

   
   

1.

 

Niech n=11, czyli jest to liczba pierwsza, czyli 

Φ

(n)=n-1=10,

  

2.

 

wybieramy d=7, a więc zgodnie z równaniem 7*e mod 10=1, odwrotnością 
liczby 7 modulo 10 jest 3. Można to obliczyć :

  

e=inv(7,10)=3

  

   

3.

 

Niech M=5 będzie tekstem jawnym do zaszyfrowania, w takim razie:

  

C=M

e

mod n = 5

3

 mod 11 = 4

  

oraz

  

M =C

d

mod n = 4

7

mod 11=5

  

Bezpieczeństwo powyższego szyfru opiera się na złożoności obliczania 
logarytmów dyskretnych w postaci:  

e=log

M

C

  

lub

  

d=log

C

M, przy czym kryptoanalityk musi dysponować tekstem jawnym i 

zaszyfrowanym.

  

Wzór szacunkowej liczby operacji niezbędnych do wykonania celem złamania 
szyfru Pohliga-Hallamana:  

Najszybszy ze znanych algorytmów obliczania logarytmów dyskretnych przy 
zadanym n będącym liczbą pierwszą potrzebuje wykonania około:

  

 
exp(sqrt(sqrt(ln(n)ln(ln(n)))) operacji tj.  
dla liczby n 200-bitowej potrzeba:2,7*10

11

 operacji do wykonania.  

 
Zakładając, ze potrzeba 100 nS  na wykonanie jednej takiej operacji, cała operacja 

deszyfracji będzie trwała około 0.1 dnia.Dla n o długości 664 bitów, liczba 
operacji wynosi ok. 1.2*10

23

 czyli zajmuje to ok. 10

11

 dni, czyli cośok. miliard 

lat.  

   
   
   
   

Szyfr RSA(Rivest-Shamir-Adleman)

 

   

Realizacja szyfru RSA:

  

Róznica między tym szyfrem a poprzednio omawianą odmianą szyfru 
wykładniczego polega na odmiennym doborze liczby n. Dobierana ona jest jako 
iloczyn dwóch wielkich liczb pierwszych p i q .

  

n=pq, z czego zgodnie z 

twierdzeniem 3

 funkcja Eulera dla n wynosi:

  

   

Φ

(n)=(p-1)*(q-1).

 

   

Wówczas:

  

1)zalecane jest wybór liczby d względnie pierwszej z 

φ

(n) oraz takiej, ze zawiera 

się ona w przedziale [(max(p.,q)

+1,n-1]

  

2)wartość e oblicza się analogicznie jak w poprzednim algorytmie szyfrowania:

  

e=inv(d,

Φ

(n))

  

z tym ,że jeśli e<log

2

n, to nie nastąpi dla każdego szyfrogramu w czasie deszyfracji 

operacja redukcji modulo n. To oznacza pewne podobieństwo bloków szyfrogramu 
do tekstu jawnego. Dlatego należy wybrać w tym przypadku nową liczbę d 
powtórzyć algorytm od punktu 1).

  

Przykład:

  

1)Niech p.=5 i q=7, czyli n=35 a 

Φ

(n)=(p-1)(q-1)=24  

2)wybieramy d=11  
3)obliczamy e=inv(11,24)=11, co oznacza akurat jednakowy wykładnik 
szyfracji i deszyfracji.  
4)Niech M.=2(tekst jawny), wówczas:  
C=M

e

mod n = 2

11

 mod 35 = 2048 mod 35 = 18  

i oczywi

ś

cie:  

M=C

d

mod n = 18

11

 mod 35 = 2 = M 

 

Bezpieczeństwo tego szyfru opiera się na trudności wyliczenia F(n), czyli na 
faktoryzacji liczby n na czynniki pierwsze(Twierdzenie 3). Liczba operacji 
potrzebna do rozkładu liczby n    na czynniki pierwsze według najszybszego 
algorytmu Schroeppela równa się szacunkowo liczbie operacji obliczania 
algorytmów dyskretnych czyli:  

exp(sqrt(ln(n)ln(ln(n)))).

  

W takim razie w przeciwieństwie do algorytmu Pohliga-Hallmana w tym 
algorytmie można podać całą procedurę szyfracji czyli liczby n i e, ponieważ z 
liczby n nie wynika w sposób prosty liczba 

Φ

(n), a ta liczba jest właśnie potrzebna 

do wyliczenia d- wykładnika potrzebnego do deszyfracji.

  

Protokół wymiany klucza w algorytmie szyfrowania RSA:

  

Załóżmy, że wymiany informacji chcą dokonać dwie osoby mianowicie: Alicja i 
Beata, przy czym Alicja jest osobą nadającą informację, a Beata jest osobą 
odbierającą zaszyfrowaną informację. W takim razie protokół wymiany kluczy 
może być następujący:  
1) Beata generuje dwie wielkie liczby pierwsze p i q i oblicza ich iloczyn n=p*q  
2) Następnie Beata na podstawie obliczonej wartości funkcji Eulera tj.  

Φ

Φ

Φ

Φ

(n)=(p-1)*(q-1)  generuje liczbę e  

3) Beata, na podstawie wygenerowanej liczby e takiej, że e>log

2n, 

z równania:  

   
ed mod 

Φ

Φ

Φ

Φ

(n) = 1, 

   
oblicza wartość liczby d  
4) Beata przekazuje liczby e i n Alicji jako swój klucz publiczny, a liczbę d  

zachowuje jako swój klucz prywatny.  
5) Na podstawie liczb n i e Alicja szyfruje wiadomość i wysyła ją do Beaty  
5) Beata posiada tylko sobie znany klucz prywatny d, komplementarny do 
klucza publicznego e i n i deszyfruje wiadomość otrzymaną od Alicji.  
 

Problem wiarygodności przesłanej wiadomości

  

Załóżmy, że w trakcie przesyłania wiadomości od Alicji do Beaty, Tomek 
przechwycił wiadomość przesyłaną przez Alicję i podmienił ją swoją informacją 
szyfrowaną ( klucz publiczny Beaty 

e i n

 jest przecież powszechnie dostępny).

  

Występuje więc problem potwierdzenia wiarygodności otrzymanej wiadomości.

  

Rozwiązuje się go przez stosowanie podpisów albo inaczej nazwanych sygnatur 
elektronicznych. W opisanym powyżej przypadku wymiany informacji między 
Alicją a Beatą, wiadomość szyfrowaną Alicja podpisuje dodatkowo, stosując swój 
klucz prywatny (zakładamy, że Beata posiada komplementarny do tego klucza 
prywatnego Alicji, klucz publiczny Alicji w swojej bazie kluczy publicznych osób 
z którymi chcę się kontaktować). W takim razie Beata posługując się kluczem 
p

u

blicznym Alicji potwierdzi autentyczność informacji.

  

Dodatkowo w pakietach szyfracji i wymiany informacji szyfrowanej takich jak 
PGP(Pretty Good Privacy), stosuje się skrót z informacji przesyłanej, generowany 
za pomocą jednokierunkowej funkcji skrótu (one - way hash function). 
Właściwością takiej funkcji jest to, że otrzymana informacja jest trudna do 
podrobienia. Tzn: że generacja tego "odcisku palca" na podstawie funkcji skrótu 
jest mało czasochłonna, ale stworzenie dokumentu fałszywego, który posiadałby 
taką samą wartość funkcji skrótu nastręcza fałszerzowi poważne problemy, 
związane z wielkimi nakładami obliczeniowymi. Inaczej mówiąc dla funkcji 
jednokierunkowych nie istnieje funkcja odwrotna, którą można by przedstawić w 
sposób jawny.

  

 

Problem generowania wielkich liczb pierwszych:

  

Gdy n jest liczbą 200-cyfrową(w układzie dziesiętnym, czyli ok. 600-bitową), to 
zachodzi potrzeba wygenerowania wielkich liczb pierwszych p i q o długości około 
100- cyfr. Oczywiście liczbę taką generuje się z prawdopodobieństwem bliskim 
jedności.

  

W tym celu:

   

•

 

generujemy liczbę b, która jest “prawdopodobnie liczbą pierwszą

  

•

 

generujemy 100 liczb a z przedziału [1,b-1]

  

•

 

liczba a jest prawie na pewno liczbą pierwszą, gdy spełnione są warunki:

  

        a)  gcd(a,b)=1 co jest oczywiste, bo liczby a i b muszą względnie pierwsze.

  

        b)  spełniona musi być równość:

  

                J(a/b)mod b=a

(b-1)/2

 mod b

  

gdzie: J(a/b) jest symbolem Jacobiego.

  

Gdy więc b nie jest liczbą pierwszą równania mogą być niespełnione z prawdp.1/2 
co dla 100 udanych prób daje prawdp. wystąpienia liczby b, która nie jest liczbą 
pierwszą równe: 1/2

100

  

Przykład 

 

long J(long a, long b)

  

{

  

 long Jac;

  

 if(a==1)

  

  Jac=1;

  

else

  

  if((a%2)==0)

  

{

  

 if((( (((int)(b*b-1))>>3) )%2)==0)

  

 Jac=J(a>>1,b);

  

else

  

 Jac=-J(a>>1,b);

  

}

  

else if(((((int)(a-1)*(b-1))>>2)%2)==0)

  

 Jac=J(b%a,a);

  

else

  

 Jac=-J(b%a,a);

  

return(Jac);

  

}

  

 
Przy użyciu powyżej zdefiniowanych w C funkcji należałoby 100-krotnie 
sprawdzic czy następujące wyrazenie jest spełnione(jest prawdz

iwe):

  

(J(a,b) %b)= =fastexp(a,(b-1)>>1,b) //w notacji języka C.