Informatyka dla klas II

Rozkład na czynniki pierwsze

Sposoby reprezentacji znaków i łańcuchów znakowych

ASCII

We współczesnych językach programowania znaki są podstawowym typem danych. W pamięci komputera znak jest przechowywany w postaci liczby, którą nazywamy kodem znaku (ang. character code). Każdy znak posiada swój własny kod. Aby różne urządzenia systemu komputerowego mogły w ten sam sposób interpretować kody znaków, opracowano kilka standardów kodowania liter. Bardzo rozpowszechniony jest standard ASCII:

ASCII – American Standard Code for Information Interchange – Amerykański Standardowy Kod do Wymiany Informacji.

Znaki są zapamiętywane w postaci 8 bitowych kodów (pierwotnie było to 7 bitów, lecz później standard ASCII został poszerzony na 8 bitów, w których znalazły się różne znaki narodowe). Taki sposób reprezentacji znaków jest dzisiaj bardzo wygodny, ponieważ podstawowa komórka pamięci komputera IBM przechowuje właśnie 8 bitów. Dzięki temu znaki dobrze mieszczą się w pamięci.

Typ ten jest w C++ reprezentowany przez char lub unsigned char. W pierwszym typie kody znaków spoza standardowego zestawu ASCII są ujemne (traktuje się je jako liczbę U2) i przyjmują wartości od -128 do -1. W drugim typie kody znaków spoza standardowego zestawu ASCII mają wartości od 128 do 255.

Przyjrzyjmy się dokładniej kodom ASCII w postaci binarnej:

Podstawowy standard ASCII definiuje kody w zakresie od 0 do 127. Bitowo jest to 7 najmłodszych bitów kodu. Pozostałe kody od 128 do 255 to rozszerzony zestaw ASCII:

podstawowy kod
ASCII

rozszerzony kod
ASCII

Kody ASCII 0-31

W zakresie kodów od 0 do 31 są znaki sterujące (ang. control characters). Spełniają one różne funkcje.

0	0	0	x	x	x	x	x
znaki sterujące

Np. kod 13 oznacza przejście do następnej linii, kod 7 to dźwięk dzwonka.

// Kody ASCII
//-----------

#include <iostream>

using namespace std;

int main()
{
    cout << char(7) << endl;
    return 0;
}

Większość z tych kodów (za wyjątkiem 0,7,8,9,10 i 13) produkuje w konsoli znakowej użyteczne znaki:

// Kody ASCII
//-----------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  for(int i = 0; i < 32; i++)
  {
    cout << "znak(" << setw(2) << i << ") = ";

    switch(i)
    {
      case  0: cout << "NUL"; break;
      case  7: cout << "BEL"; break;
      case  8: cout << "BS";  break;
      case  9: cout << "HT";  break;
      case 10: cout << "LF";  break;
      case 13: cout << "CR";  break;
      default: cout << char(i); break;
    }

    cout << endl;
  }

  return 0;
}

Kody 32-127

W tym zakresie mamy podstawowe znaki pisarskie. Kod 32 oznacza spację.

// Kody ASCII
//-----------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  for(int i = 0; i < 32; i++)
  {
    for(int j = 1; j <= 3; j++)
      cout << "znak(" << setw(3) << i + 32 * j << ") = "
           << char(i + 32*j) << "   ";
    cout << endl;
  }
  return 0;
}

Cyfry mają kody od 48 (0) do 57 (9).

0	0	1	1	x	x	x	x
cyfry

W powyższym kodzie xxxx jest wartością binarną cyfry: 0000 = 0, 0001 = 1, 0010 = 2, ..., 1001 = 9.

// Kody ASCII
//-----------

#include <iostream>

using namespace std;

int main()
{
  for(int i = 48; i < 58; i++)
    cout << "znak(" << i << ") = " << char(i) << endl;

  return 0;
}

Litery duże mają kody od 65 (A) do 89 (Z). Litery małe mają kody od 97 (a) do 122 (z).

litery duże

litery małe

W powyższych kodach xxxxx oznacza binarny numer litery od 00001 = 1 do 11010 = 26. Zwróć uwagę, że litery małe różnią się od dużych bitem b₅. Oznacza to, że np. kod litery 'a' jest większy o 32 od kodu litery 'A'. Aby z kodu dużej litery otrzymać kod małej, wystarczy ustawić na 1 bit b₅. Podobnie, aby z kodu małej litery otrzymać kod duże, wystarczy wyzerować bit b₅.

// Kody ASCII
//-----------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  for(int i = 1; i < 27; i++)
  {
    for(int j = 0; j < 2; j++)
      cout << "znak(" << setw(3) << i + 64 + 32 * j << ") = "
           << char(i + 64 + 32 * j) << "   ";
    cout << endl;
  }

  return 0;
}

Kody 128-255

Są to rozszerzone kody ASCII. Ich interpretacja zależy od tzw. strony kodowej, która jest wybrana w systemie. Kody znaków rozszerzonych mogą być traktowane jako liczby ujemne.

// Kody ASCII
//-----------

#include <iostream>

using namespace std;

int main()
{
  for(int i = 0; i < 32; i++)
  {
    for(int j = 0; j < 4; j++)
      cout << "znak("
           << 128+i+j*32
           << ") = "
           << char(128+i+j*32)
           << "   ";
    cout << endl;
  }
  return 0;
}

W polskich systemach Windows w konsoli znakowej jest zwykle wykorzystywana strona kodowa CP852. Niestety, sam system Windows wykorzystuje standard Windows 1250, w którym polskie literki posiadają inne kody niż ich odpowiedniki w konsoli znakowej.

	Ą	Ć	Ę	Ł	Ń	Ó	Ś	Ź	Ż	ą	ć	ę	ł	ń	ó	ś	ź	ż
Windows 1250	165	198	202	163	209	211	140	143	175	185	230	234	179	241	243	156	159	191
CP852	164	143	168	157	227	224	151	141	189	165	134	169	136	228	162	152	171	190
ósemkowo	244	217	250	235	343	340	227	215	275	245	206	251	210	344	242	230	253	276

Konsekwencją tego faktu jest to, że program napisany w edytorze pracującym w Windows nie będzie poprawnie wyświetlał polskich znaków (tablica znakowa s zawiera kody polskich znaków Windows 1250):

// Kody ASCII
//-----------

#include <iostream>

using namespace std;

int main()
{
  unsigned char s[] = "ĄĆĘŁŃÓŚŹŻąćęłńóśźż*";

  cout << "Windows 1250" << endl << endl;
  for(int i = 0; s[i] != '*'; i++)
    cout << s[i] << " : " << (int) s[i] << endl;
  return 0;
}

Należy dokonać odpowiedniej konwersji (tablica znakowa t zawiera poprawne kody polskich znaków dla konsoli CP852):

// Kody ASCII
//-----------

#include <iostream>

using namespace std;

int main()
{
  unsigned char s[] = "ĄĆĘŁŃÓŚŹŻąćęłńóśźż*";
  unsigned char t[] = {164,143,168,157,227,224,151,141,189,
                       165,134,169,136,228,162,152,171,190};

  cout << "Windows 1250" << endl << endl;
  for(int i = 0; s[i] != '*'; i++)
    cout << t[i] << " : " << (int) s[i] << endl;
  return 0;
}

Problemy te znikają, jeśli zrezygnujemy z polskich znaków w trybie konsoli lub będziemy tworzyć tylko aplikacje dla GUI w Windows. Należy wspomnieć, że w systemie Linux nie występuje ten problem, ponieważ kodowanie polskich znaków jest jednolite w całym systemie (ale z kolei jest to jeszcze inna strona kodowa – ISO-8859-2, która jest standardem ogólnoświatowym). Jak widać, polscy programiści lekko nie mają.

Przechowywanie tekstu

Tekst jest przechowywany w pamięci w postaci ciągu znaków. Na końcu tego ciągu umieszczany jest znak o kodzie 0 (NUL). Ten sposób zapisu tekstów nosi nazwę cstring (ang. łańcuch znakowy typu C). Jest on powszechnie stosowany w języku C++.

Teksty możemy przechowywać w tablicach znakowych:

// Łańcuchy znakowe
//-----------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  char s[] = "Pewien tekst"; // inicjujemy tablicę
  int i;

  cout << s << endl << endl; // wyświetlamy zawartość tablicy

  i = 0;       // indeks pierwszego znaku w tablicy s
  do
  {
    cout << "s[" << setw(2) << i << "] = \""
         << s[i] << "\" kod " << setw(3) << (int) s[i] << endl;
  } while(s[i++]); // pętlę kończymy po osiągnięciu kodu NUL

  cout << endl;

  return 0;
}

Zwróć uwagę, że przy inicjalizacji tablicy:

char s[] = "...";

automatycznie zostaje wstawiony na koniec znak NUL. Tablica przyjmuje taki rozmiar, aby pomieścić wszystkie znaki tekstu wraz ze znakiem NUL.

Tekst można odczytać z konsoli do tablicy znakowej za pomocą strumienia cin. Jednakże należy się przy tym zatroszczyć, aby tablica miała odpowiednio duży rozmiar. Prosty odczyt ze strumienia cin zwraca jeden wyraz, ponieważ spacja jest traktowana jako separator.

// Łańcuchy znakowe
//-----------------

#include <iostream>

using namespace std;

int main()
{
  char n[100]; // Odpowiednio duża tablica znakowa

  cout << "Podaj swoje Imi\251 : ";
  cin >> n;
  cout << endl
       << "Witaj, " << n << endl
       << "Ja jestem C++" << endl;

  return 0;
}

Pracując w konsoli, możesz bez problemu wprowadzać polskie znaki. Musisz jedynie pamiętać, iż posiadają one kody CP852, a nie Windows 1250. Będzie to miało znaczenie przy porównywaniu znaków.

Jeśli chcesz odczytać cały wiersz znaków, to musisz skorzystać z funkcji składowej strumienia cin o nazwie getline(). Funkcja ta posiada następujące parametry:

cin.getline(s,n);

lub

cin.getline(s,n,d);

s – tablica znakowa lub wskaźnik do danych char. Tutaj zostanie umieszczony wiersz znaków.
n – maksymalny rozmiar tablicy s. Określa liczbę znaków wraz z NUL, które mogą być umieszczone w s.
d – znak końca wiersza. Jeśli będzie pominięty, to znakiem tym jest '\n'. Znak jest usuwany ze strumienia, lecz nie trafia do s.

// Łańcuchy znakowe
//-----------------------------------

#include <iostream>

using namespace std;

int main()
{
  char n[100],a[100],c[100];

  cout << "Podaj kolejno:" << endl << endl;
  cout << "Imi\251 i nazwisko    : "; cin.getline(n,100);
  cout << "Adres zamieszkania : ";    cin.getline(a,100);
  cout << "Kraj urodzenia     : ";    cin.getline(c,100);

  cout << endl
       << "Nazywasz si\251 " << n << "." << endl
       << "Mieszkasz na ulicy " << a << "." << endl
       << "Kraj twoich narodzin to " << c << "." << endl;

  return 0;
}

Problem może pojawić się, jeśli czytasz naprzemiennie z cin oraz z cin.getline(). Sprawdź poniższy program. Odczytuje on najpierw liczbę z cin. Następnie czyta wiersz znaków za pomocą funkcji getline(). I na koniec ponownie czyta liczbę z cin.

// Łańcuchy znakowe
//-----------------

#include <iostream>

using namespace std;

int main()
{
  char s[100];
  int a,b;

  cout << "Liczba : "; cin >> a;
  cout << "Wiersz : "; cin.getline(s,100);
  cout << "Liczba : "; cin >> b;

  cout << a << endl
       << s << endl
       << b << endl;

  return 0;
}

Co tutaj się stało? Gdy wprowadziłeś pierwszą liczbę (u mnie 20), to komputer nie zaczekał na wprowadzenie wiersza, lecz od razu przeszedł do odczytu drugiej liczby. Dlaczego? Otóż strumień cin po odczycie pierwszej liczby pozostawił w sobie znak końca wiersza '\n'. Gdy teraz wywołaliśmy funkcję getline(), to natrafiła ona od razu na ten znak i zakończyła odczyt. W efekcie użytkownik nie miał szansy wprowadzić swojego tekstu. Funkcja getline() usunęła ze strumienia znak '\n', a program przeszedł do odczytu drugiej liczby.

Jak rozwiązać ten problem? Musimy użyć funkcji ignore(), która pobiera ze strumienia cin zadaną liczbę znaków, aż do napotkania znaku ograniczającego:


			cin.ignore(n,d);

n – liczba znaków do pominięcia.
d – znak ograniczający.

// Łańcuchy znakowe
//-----------------

#include <iostream>

using namespace std;

int main()
{
  char s[100];
  int a,b;

  cout << "Liczba : "; cin >> a;           // czytamy pierwszą liczbę
  cin.ignore(1000,'\n');                   // ze strumienia usuwamy znak EOL
  cout << "Wiersz : "; cin.getline(s,100); // czytamy wiersz
  cout << "Liczba : "; cin >> b;           // czytamy drugą liczbę

  cout << a << endl                        // pierwsza liczba
       << s << endl                        // wiersz
       << b << endl;                       // druga liczba

  return 0;
}

Ze strumienia cin możemy również pobierać pojedyncze znaki oraz ich ciągi za pomocą funkcji get():

kod = cin.get();   // zwraca kod ASCII znaku

cin.get(c);        // umieszcza znak w zmiennej znakowej c

cin.get(s,n);      // odczytuje n-1 znaków do tablicy znakowej s, dodając na końcu NUL

cin.get(s,n,d);    // jak wyżej, lecz do napotkania znaku ograniczającego d

// Łańcuchy znakowe
//-----------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int code;

  cout << "Wpisz wiersz : ";

  while((code = cin.get()) != '\n')
    cout << (char) code << " = " << setw(3) << code << endl;

  return 0;
}

Podsumowanie

Zmienna znakowa:

char c;           // kody rozszerzone ASCII -1...-128

unsigned char c;  // kody rozszerzone ASCII 128...256

Tekst jest utworzony z ciągu znaków zakończonych kodem NUL.

Tablica znakowa:

char s[liczba_znaków + 1];

unsigned char s[liczba_znaków + 1;

Inicjalizacja tablicy znakowej tekstem (znak NUL jest automatycznie dołączany na koniec tekstu, a tablica przyjmuje odpowiedni rozmiar):

char s[] = "dowolny tekst";

unsigned char s[] = "dowolny tekst";

Zapis do strumienia cout:

cout << (int) c;                // kod znaku

cout << (int)(unsigned char) c; // kod znaku rozszerzonego ASCII

cout << (char) kod;             // znak o danym kodzie

cout << s;                      // zapis tablicy znakowej

Odczyt ze strumienia cin:

cin >> s;           // odczyt wyrazu, spacja i /n są znakami rozdzielającymi

kod = cin.get();    // kod znaku ze strumienia

cin.get(c);         // znak ze strumienia

cin.get(s,n);       // odczyt n znaków ze strumienia do tablicy s

cin.get(s,n,d);     // odczyt do n znaków do tablicy s, aż do napotkania znaku d

cin.getline(s,n);   // odczyt do n znaków do tablicy s, aż do napotkania \n

cin.getline(s,n,d); // odczyt do n znaków do tablicy s, aż do napotkania znaku d

cin.ignore(n,d);    // usuwa ze strumienie do n znaków aż do napotkania znaku d, który również usuwa

Proste zadania

Napisz funkcje:
bool IsDigit(char c); - zwraca true, jeśli znak c jest cyfrą 0...9 bool IsXDigit(char c); - zwraca true, jeśli znak c jest cyfrą szesnastkową bool IsAlpha(char c); - zwraca true, jeśli znak c jest literą, również polską CP852 bool IsLower(char c); - zwraca true, jeśli znak c jest małą literą, również polską CP852 bool IsUpper(char c); - zwraca true, jeśli znak c jest dużą literą, również polską CP852
Powyższe funkcje wykorzystaj do rozbioru wiersza na znaki cyfr, liter dużych i małych.
Napisz funkcje:
char ToCP852(char c); - zamienia znak w standardzie Windows 1250 na znak w standardzie CP852 char To1250(char c); - zamienia znak w standardzie CP852 na znak w standardzie Windows 1250 char * StrToLower(char * s); - zamienia w tablicy s litery duże na małe, w tym również polskie znaki CP852 char * StrToUpper(char * s); - zamienia w tablicy s litery małe na duże, w tym również polskie znaki CP852 char * StrToCP852(char * s); - zamienia w tablicy s znaki w standardzie Windows 1250 na CP852 char * StrTo1250(char * s); - zamienia w tablicy s znaki w standardzie CP852 na Windows 1250
Wykorzystaj powyższe funkcje w prostym programie, który odczytuje wiersz znaków, zamienia go na małe litery, wyświetla, zamienia na duże litery i ponownie wyświetla. W programie wypisuj wszystkie teksty po polsku.

Szyfr Cezara

Szyfrowanie tekstów (ang. text encryption) ma na celu ukrycie ważnych informacji przed dostępem do nich osób niepowołanych. Historia kodów szyfrujących sięga czasów starożytnych. Już tysiące lat temu egipscy kapłani stosowali specjalny system hieroglifów do szyfrowania różnych tajnych wiadomości. Szyfr Cezara (ang. Ceasar's Code lub Ceasar's Cipher) jest bardzo prostym szyfrem podstawieniowym (ang. substitution cipher). Szyfry podstawieniowe polegają na zastępowaniu znaków tekstu jawnego (ang. plaintext) innymi znakami przez co zawarta w tekście informacja staje się nieczytelna dla osób niewtajemniczonych. Współcześnie szyfrowanie stanowi jedną z najważniejszych dziedzin informatyki – to dzięki niej stał się możliwy handel w Internecie, funkcjonują banki ze zdalnym dostępem do kont, powstał podpis elektroniczny oraz bezpieczne łącza transmisji danych. Przykładów zastosowania jest bez liku i dokładne omówienie tej dziedziny wiedzy leży daleko poza możliwościami tego artykułu.

Szyfr Cezara został nazwany na cześć rzymskiego imperatora Juliusza Cezara, który stosował ten sposób szyfrowania do przekazywania informacji o znaczeniu wojskowym. Szyfr polega na zastępowaniu liter alfabetu A...Z literami leżącymi o trzy pozycje dalej w alfabecie:

Tekst jawny

Szyfr Cezara

Ostatnie trzy znaki X, Y i Z nie posiadają następników w alfabecie przesuniętych o trzy pozycje. Dlatego umawiamy się, iż alfabet "zawija się" i za literką Z następuje znów litera A. Teraz bez problemu znajdziemy następniki X → A, Y → B i Z → C.

Przykład:

Zaszyfrować zdanie: NIEPRZYJACIEL JEST BARDZO BLISKO.

Poszczególne literki tekstu jawnego zastępujemy literkami szyfru Cezara zgodnie z powyższą tabelką kodu. Spacje oraz inne znaki nie będące literami pozostawiamy bez zmian:

NIEPRZYJACIEL JEST BARDZO BLISKO
QLHSUCBMDFLHO MHVW EDUGCR EOLVNR

Deszyfrowanie tekstu zaszyfrowanego kodem Cezara polega na wykonywaniu operacji odwrotnych. Każdą literę kodu zamieniamy na literę leżącą o trzy pozycje wcześniej w alfabecie.

Szyfr Cezara

Tekst jawny

Podobnie jak poprzednio trzy pierwsze znaki szyfru Cezara nie posiadają bezpośrednich odpowiedników liter leżących o trzy pozycje wcześniej, ponieważ alfabet rozpoczyna się dopiera od pozycji literki D. Rozwiązaniem jest ponowne "zawinięcie" alfabetu, tak aby przed literą A znalazły się trzy ostatnie literki X, Y i Z.

Do wyznaczania kodu literek przy szyfrowaniu i deszyfrowaniu posłużymy się operacjami modulo. Operacja modulo jest resztą z dzielenia danej liczby przez moduł. Wynik jest zawsze mniejszy od modułu. U nas moduł będzie równy 26, ponieważ tyle mamy liter alfabetu.

Jeśli c jest kodem ASCII dużej litery alfabetu (rozważamy tylko teksty zbudowane z dużych liter), to szyfrowanie kodem Cezara polega na wykonaniu następującej operacji arytmetycznej:

c = 65 + (c - 62) mod 26

Deszyfrowanie polega na zamianie kodu wg wzoru:

c = 65 + (c - 42) mod 26

Algorytm szyfrowania tekstu kodem Cezara

Wejście

Łańcuch tekstowy s

Wyjście:

Łańcuch tekstowy s zaszyfrowany kodem Cezara

Elementy pomocnicze:

i	–	indeks, i N
kod(x)	–	zwraca kod litery x
znak(x)	–	zamienia kod x na odpowiadający mu znak ASCII

Lista kroków:

K01:	Dla i = 0,1,...,\|s\| - 1 wykonuj K02...K03	; przeglądamy kolejne znaki tekstu
K02:	Jeśli s[i] < "A" ∨ s[i] > "Z", to następny obieg pętli K01	; pomijamy znaki nie będące literami A...Z
K03:	s[i] ← znak(65 + (kod(s[i]) - 62) mod 26)	; szyfrujemy szyfrem Cezara
K04:	Pisz s
K05:	Zakończ

Algorytm deszyfrowania tekstu zaszyfrowanego kodem Cezara

Wejście

Łańcuch tekstowy s zaszyfrowany kodem Cezara

Wyjście:

Tekst jawny

Elementy pomocnicze:

i	–	indeks, i N
kod(x)	–	zwraca kod litery x
znak(x)	–	zamienia kod x na odpowiadający mu znak ASCII

Lista kroków:

K01:	Dla i = 0,1,...,\|s\| - 1 wykonuj K02...K03	; przetwarzamy kolejne znaki tekstu
K02:	Jeśli s[i] < "A" ∨ s[i] > "Z", to następny obieg pętli K01	; pomijamy znaki nie będące literami A...Z
K03:	s[i] ← znak(65 + (kod(s[i] - 42) mod 26)	; deszyfrujemy
K04:	Pisz s
K05:	Zakończ

Szyfrowanie z pseudolosowym odstępem

Szyfr Cezara posiada kilka wad, które uniemożliwiają praktyczne zastosowanie. Po pierwsze wystarczy odkryć wartość przesunięcia kodów (oryginalnie wynosi ono 3, lecz można je zmieniać w zakresie od 1 do 25), aby rozszyfrować całą wiadomość. W tym celu należy przeprowadzić 25 prób, co dla współczesnych komputerów nie stanowi żadnego problemu.

Przesunięcie kodów	Szyfr
0	ALA MA KOTA
+ 1	BMB NB LPUB
+ 2	CNC OC MQVC
+ 3	DOD PD NRWD
+ 4	EPE QE OSXE
+ 5	FQF RF PTYF

Po drugie, z uwagi na stałe przesunięcie kodów, te same znaki są zawsze szyfrowane tak samo. Jeśli na przykład zaszyfrujemy AAAAAAAAAA, to otrzymamy ciąg DDDDDDDDDD.

Aby znacząco utrudnić rozszyfrowanie wiadomości zaprojektujemy szyfr, w którym przesunięcie kodów będzie się zmieniało w zakresie od 0 do 25 w trakcie szyfrowania znaków. Do tego celu potrzebna nam jest możliwość generacji tych samych ciągów liczbowych przy szyfrowaniu oraz rozszyfrowywaniu. Wykorzystamy generator pseudolosowy LCG, który startując od określonego ziarna tworzy zawsze te same ciągi liczb pseudolosowych. Kluczem szyfrującym będą parametry generatora oraz wartość ziarna pseudolosowego. Parametry generatora: moduł m, mnożnik a oraz przyrost c zostaną na stałe zdefiniowane w programie (możesz je zmienić, wtedy zmianie ulegnie sposób szyfrowania). Użytkownik będzie jedynie podawał wartość ziarna pseudolosowego X_o. Sposób projektowania generatora LCG opisaliśmy w rozdziale o liczbach pseudolosowych.

Projekt generatora LCG

Im większy zakres generowanych liczb pseudolosowych, tym dłuższy okres powtarzania tworzonego ciągu. W efekcie trudniejsze jest złamanie szyfru. Kryptologia potrafi bez większych problemów łamać szyfry oparte na prostych generatorach pseudolosowych z uwagi na ich właściwości, dlatego nie są one stosowane w praktycznych systemach szyfrowania – użyty generator musi być kryptologicznie bezpieczny. My się tym nie będziemy przejmowali, ponieważ nasz projekt jest czysto dydaktyczny.

Wybieramy zakres od 0 do X_max = 3956279999.

Moduł m jest równy X_max + 1 = 3956280000

Czynniki pierwsze modułu m = 3956280000 = 2 × 2 × 2 × 2 × 2 × 2 × 3 × 5 × 5 × 5 × 5 × 32969

Przyrost c = 7 × 11 × 17 = 1309

Mnożnik a - 1 = 2 × 2 × 3 × 5 × 32969 = 1978140, stąd a = 1978141.

Podsumowując otrzymujemy następujący generator LCG:

LCG(3956280000,1978141,1309,X_o)

Ziarno X_o jest w zakresie od 0 do X_max, czyli od 0 do 3956279999. Liczba ta będzie naszym kluczem szyfrującym.

Szyfrowanie

Zasada szyfrowania jest następująca:

Odczytujemy klucz i wprowadzamy go do ziarna pseudolosowego naszego generatora LCG. Na podstawie tego klucza generator LCG będzie tworzył ściśle określony ciąg liczb pseudolosowych. Odczytujemy następnie łańcuch s, który ma zostać zaszyfrowany. Zamieniamy wszystkie litery z małych na duże (nasz algorytm szyfruje tylko duże znaki). Przetwarzamy kolejne znaki tego łańcucha. Dla każdego znaku generujemy liczbę pseudolosową X. Teraz sprawdzamy, czy przetwarzany znak łańcucha s jest dużą literą od A do Z. Jeśli tak, to obliczamy jego kod ch i przekształcamy go zgodnie ze wzorem:

ch = 65 + (ch - 65 + X mod 26) mod 26

Wynik jest kodem zaszyfrowanego znaku – umieszczamy go w łańcuchu s na miejscu przetwarzanego znaku i kontynuujemy te same operacje aż do przetworzenia wszystkich znaków w s. Na końcu łańcuch s zwracamy jako wynik szyfrowania.

Algorytm szyfrowania z pseudolosowym odstępem

Wejście

X	–	klucz, X N
m,a, c	–	parametry generatora LCG, m,a,c N
s	–	łańcuch tekstowy

Wyjście:

Zaszyfrowany łańcuch s

Elementy pomocnicze:

i	–	indeks, i N
kod(x)	–	zwraca kod litery x
znak(x)	–	zamienia kod x na odpowiadający mu znak ASCII

Lista kroków:

K01:	Dla i = 0,1,...,\|s\| - 1, wykonuj K02...K04	; przetwarzamy kolejne znaki łańcucha s
K02:	X ← (a × X + c) mod m	; obliczamy nową liczbę pseudolosową
K03:	Jeśli s[i] < 'A' ∨ s[i] > 'Z', to następny obieg pętli K01	; pomijamy znaki nie będące literami od A do Z
K04:	s[i] = znak(65 + (kod(s[i]) - 65 + X mod 26) mod 26)	; szyfrujemy
K05:	Pisz s	; wyprowadzamy szyfr
K06:	Zakończ	; gotowe

Deszyfrowanie

Zasada rozszyfrowywania jest prawie identyczna jak przy szyfrowaniu. Jedyna różnica leży we wzorze obliczania kodu znaku z kodu szyfru:

ch = 65 + (ch - 39 - X mod 26) mod 26

Algorytm deszyfrowania z pseudolosowym odstępem

Wejście

X	–	klucz, X N
m, a, c	–	parametry generatora LCG, m,a,c N
s	–	zaszyfrowany łańcuch tekstowy

Wyjście:

Rozszyfrowany łańcuch s

Elementy pomocnicze:

i	–	indeks, i N
kod(x)	–	zwraca kod litery x
znak(x)	–	zamienia kod x na odpowiadający mu znak ASCII

Lista kroków:

K01:	Dla i = 0,1,...,\|s\| - 1, wykonuj K02...K04	; przetwarzamy kolejne znaki łańcucha s
K02:	X ← (a × X + c) mod m	; obliczamy nową liczbę pseudolosową
K03:	Jeśli s[i] < 'A' ∨ s[i] > 'Z', to następny obieg pętli K01	; pomijamy znaki nie będące literami od A do Z
K04:	s[i] = znak(65 + (kod(s[i]) - 39 - X mod 26) mod 26)	; rozszyfrowujemy
K05:	Pisz s	; wyprowadzamy tekst
K06:	Zakończ	; gotowe