Page 155 - ISCI’2017

1 Method of multimodulo transformation in the finite field

Let us consider PRS generation method with certain symbols alphabet, for example m, on based on

p
n
GF
arbitrary Galois field ( ). For general case we will think that there is made up k transformations
n
p
of units of Galois field GF ( ) extension, corresponding to modules
( f ( ) ( )) ( fXfX , 1 , 1 ( ) ( )),, f 2 X  , ( f k 2 ( ) f , k 1 − ( )) and the last module m. General options which are
X
X
X
−
(
enough to generate elements a of ( ) field is tuple ( ) pXf , , n θ, j ), where ( ) – irreducible
n
p
X
GF
f
i
polynomial of degree n over finite field GF ( ) p , and θ – primary element chosen from magnitude
j
{ } θ of division (pϕ n − ) 1 , where ( ) – Euler’s function [8]. In such a case generation of field
ϕ
elements is carried out according to the rule:
a = ( ) (mod θ j i ( f ( ) pX , n , )). (1)
i
(
It is shown [9], that if the above-said requirements to tuple ( ) pXf , , n θ , j ) have been fulfilled, (1)
would generate finite Galois field with repetition period p n − 1. Let us denote that above-said is true
for p = 7 , 5 , 3 , 2 and subsequent prime numbers. When p = 2 , there will be extension of Galois field

F ( ) 2 .

In the following, let ( f s ( ) pX , s n , s ) be tuple of general options, for example of polynomials

(among them irreducible) ( ), =s ( ,1 −k ) 1 , and n – their degrees, from this point on we need
f
X
s
s
irreducibility of polynomials to provide their coprimality when necessary [9].
Also let degrees of polynomials (among them irreducible) n fulfill requirements:
s
n > n , n > n , …, n k − 2 > n , (2)
1 −
2
2
k
3
1
wherein basis of m alphabet is any number, besides ineqautions are fulfilled:
2 n
3 n
1 n
p >> p , p 2 n >> p ,…, p k n − 2 >> p k n 1 − , p k n −1 >> m. (3)
The statement 1 is fair.
Statement 1.
Deterministic PRS generator, which is functioning according to algorithm of multimodulo
transformations:

( ) (mod
b = (θ j i ( f ( ) ,, pX n ) ( , f 1 ( ), pX 1 ,n 1 ) ( , f 2 ( ), pX 2 ,n 2 ) , (4)
i
m
X ,
 , ( f k 1− ( ) pX , k 1− n , k 1− ) ( f, m ( ) )),
where ( )( f s X p , s n , s ) – tuple of general options, m – certain integer, k – degree of multi modularity,

p – number (not necessarily prime), m – positive integer, provides generation of PRS (symbols)
m
155