Reprezentace celých čísel

• standardně je celé číslo a reprezentováno jedním slovem délky n ; v takovéto reprezentaci je velikost čísla a omezena a < 2^n-1 ; tato maximální velikost je např. pro n = 16, a < 32 768 , pro n = 32, a < 2 147 483 648 a pro n = 64, a < 9 223 372 036 854 775 808

• potřebujeme však reprezentovat libovolně velké celé číslo, viz např. pseudo-zbytky při výpočtu gcd

• jednou možností reprezentace velkého celého čísla a je reprezenatce polem A , přičemž všechny prvky pole A_i < 2^n-1 a platí
  
  $$a = \sum_{i=0}^m A_i \left( 2^{n-1} \right)^i$$
  
  

• čili číslo je vyjádřeno v soustavě se základem 2^n-1

• samozřejmě vždy máme omezenou paměť a tudíž vždy do této paměti můžeme uložit jen číslo omezené velikosti; pomocí této reprezentace však již můžeme pracovat s dostatečně velkými čísly, např. do 1 kB paměti můžeme uložit celé číslo až do řádu 10²⁵⁸⁸