# Impact of migration on the system of the servicing Bank

Migration of the Bank to the IPC has a smaller impact on the host of the servicing Bank compared to the host of the Issuer. The servicing Bank must upgrade the software modules for managing devices of its host application in order to ensure that chip related data is received from the terminal and sent to the Issuer’s host without meaningful processing of this data. Two options are usually used for transmitting chip related data to the Issuer’s host: a composite data element 055 that is specifically designed for the purposes in question in ISO 8583 messages, or an extension of the ISO 8583 standard that uses an extended 192-bit bitcard. Recall that the ISO 8583 standard requires the use of a bitcard up to 128 bits in size.

Minimum set of chip data in the authorization request and clearing message

1 Application Cryptogram (TC/ARQC or AAC) ‘9F26’ b 8

2 Cryptogram Information Data ‘9F27’ b 1

3 Issuer Application Data (IAD) ‘9F10’ b Var. up 32

4 Unpredictable Number ‘9F37’ b 4

5 Application transaction counter (ATC) ‘9F36’ b 2

6 Terminal Verification Result ’95’ b 5

7 Transaction Date ’9A* n 3

8 Transaction Type 9C n 1

9 Amount, Authorized ‘9F02’ n 6

10 Transaction Currency Code ’5F2A’ n 2

11 Application Interchange Profile ’82’ b 2

12 Terminal Country Code 9F1A* n 2

13 Amount Other ’9F03’ n 6

The minimum set of chip data transmitted in the authorization request from the servicing Bank to the Issuer, as well as present in the clearing message of the servicing Bank, in accordance with the EMV standard. This data set can be expanded at the discretion of a particular payment system.

Note that currently, in the leading payment systems, not all the data listed in the table is transmitted to the Issuer in a clearing message. For example, the transfer of a transaction cryptogram is optional, and the servicing Bank must only store cryptograms of transactions performed in its devices and present them to issuers upon their request.

Minimum set of chip data in the Issuer’s response to the authorization request

Number

element

data Name Tag Format Length,

byte Assignment

1 Issuer

Authentication

Data ’91’ b from 8 to 16 Provides

data,

required data for

authentication

of the Issuer

2 Issuer Script

Template 1

Template 2 7G

’72’ b to 128 Allows

to the card Issuer

teams

During transaction processing, the terminal can transmit different values of the random variable Unpredictable Number to the card at various stages of the operation. The authorization request must contain the value of this value contained in the data of the first GENERATE AC command. The clearing message must contain the last value of the Unpredictable Number received by the card from the terminal. The servicing Bank receives this value from the terminal.

The minimum set of chip data that should be contained in the Issuer’s response to the authorization request.

Conclusion

The EMV standard is still very young. In addition to the fact that it has not yet celebrated even its 10-year anniversary, we must admit that the real mass implementation of the EMV standard began only 3-5 years ago.

Experience-the “son of difficult errors” – is the main source of numerous technical refinements of the EMV standard. Incompatibility of cards and terminals due to ambiguous understanding of certain provisions of the standard by card equipment and card suppliers, or the presence of contradictions within the standard, leads to the fact that it continues to undergo minor changes. This process is natural, and today we can state that the peak of technical refinements of the standard has already passed and the intensity of their appearance is on the wane.

The EMV standard has also undergone a number of more significant changes of a technological nature during its existence. These include the definition of a new method of dynamic authentication of the card CDA to ensure the integrity of data exchange between card and terminal using a new data element Card Status Update as an alternative procedure, the script processing and maintaining the integrity of data exchange between card and terminal when using Format 2 of the ARPC cryptogram.

Of course, the appearance of Common Core Definitions specifications in the latest version of the EMV 4.1 standard is a landmark, based on which the development of the Common payment Application (CPA) card application for leading payment systems has been completed. The draft CPA standard has already been published by EMVCo and, obviously, many banks will start using it. This is due, on the one hand, to a reduction in the costs/efforts of banks for the development, implementation and maintenance of risk management procedures, card personalization, and application software of processing centers, and on the other— to the fact that the functionality of the SRA specifications fully corresponds to, and in some cases exceeds, the functionality of today’s standards of leading payment systems.

Of great importance is also the appearance of the EMV Card Personalization Specification, which allows to significantly standardize the process of personalization of Bank cards of the EMV standard.

It should be noted that changes to the standard are caused not only by new technological needs of the market, but also by new features of cards. Today, MPCs with RAM of 4-8 KB, non-volatile rewritable memory EEPR0M 32-64 KB, with 32-bit processors running at a clock frequency of up to 33-66 MHz are not a novelty. New features of the card allow you to implement mechanisms that were previously impossible to dream of.

There were changes in the first book of the EMV standard, which defines the physical characteristics of the card and terminal. For example, the world is beginning to move towards chips that consume less power and operate using a supply voltage of 3 or even 1.8 volts. This is reflected in the EMVCo policy. Currently, cards that support only 5 volts are being migrated to cards that support two voltage values of 5 and 3 volts, and cards that support three voltage values of 5, 3 and 1.8 volts. The migration process should be completed by the end of June 2009. Since July 2009 payment systems will use cards that support two or three power supply voltage values. Cards that support a single 5-volt supply voltage will be retired.

The EMV standard has yet to change. First of all, they will concern telecommunications protocols. The t=0 and T=1 protocols are outdated and do not meet today’s business requirements. They are replaced by high-speed physical layer protocols based, for example, on the use of the USB standard. In addition, the card will support network and transport layer protocols. The IP and TCP protocols will be selected as the latter. Implementing the entire Protocol stack on the card will make it an independent secure General-purpose hardware and software platform and expand the scope of application of microprocessor cards. In particular, the card will become an independent device that can work with network computers over the Internet.

When we talk about the card’s communication support, we can’t say anything about contactless cards. ISO 14443 a standard&B is becoming more and more popular in the field of financial applications, opening up new opportunities for businesses to use microprocessor cards. It is expected that the trend towards increasing the use of contactless microprocessor cards will only increase.

Over time, the EMV standard will not avoid changes related to the card’s support for payment terminal authentication. With the growing capabilities of the card, it is not difficult to do this today. It is expected that payment terminals will become a target of fraudsters at a certain stage of card migration to the new technology. It would be useful to anticipate the intentions of scammers in this direction.

Speaking about the business environment of migration to the EMV standard, we must still recognize that in the coming years, card fraud will remain the main driver of this migration. At the same time, the possibilities of contactless cards, methods of biometric authentication of the cardholder, and the use of multi-payment cards will also not remain in the shadows and will have an impact on banking technologists from their side.

In any case, it is obvious that migration to the IPC is a natural stage in the development of card technology, and all of us in the coming decades will have to become more familiar with this technology and increasingly apply it in our work.

Applications

A. Mathematical foundations of cryptography

Brief information about the mathematical foundations of cryptography will help you understand the features of many well-known cryptographic algorithms. Let’s start with the definition of the most important concepts, and also give the results of algebra used in the initial course of cryptography.

An integer a divides another integer b, symbolically this is denoted by a\B if and only if b = da for some integer d. In this case, a is called a divisor or multiplier of B.

Let o be an integer greater than 1. Then a is called a Prime number if its only divisors are 1 and a itself. Otherwise, a is called a composite number. Any integer n > 1 can be represented in a unique way up to the order of multipliers as a product of Prime numbers (the main theorem of arithmetic).

The largest common divisor of the numbers o and b is denoted by the NODE (o, b), or simply (a, b), is the largest integer that divides both a and b. in Other words, (a, b) is the only natural number that divides o and b and itself divides into any integer that divides both a and b.

The smallest common multiple of a and b, H0K(a, b), is the smallest natural number divisible by both o and b.

The greatest common divisor of a and b (o > b) can be calculated using Euclid’s algorithm. The algorithm is represented by the following chain of equalities:

a = bqi + c1, 0 < C: < b;

B = C^2+C2, 0 <SG<C1;

SG = c2d3+su 0 < S3 < SG;

Sch = c^qk+ SK, O < SK< SKH;

SK-1 = CA+1‘

Stopping the algorithm is guaranteed, since the remainder of the division of C. forms a strictly decreasing sequence of natural numbers.

From the above chain of equations, we get that SK={a, B). Indeed, it follows from the last lower equation of the chain that SK\sk_u From the penultimate equation given that ck\ck V we get that SK\SK2. Going up, we consistently prove that SC\SC Y …, ck\cv ck\b, SC\a. In other words, SK is the common divisor of a and B.

Let g now divide a and b (g is an arbitrary divisor of a and B). Then from the first equation of the chain we get that g\C, from the second-that g|S2. Going down to the lower equation, we get that g|SG i.e. we prove that SK= (a, B).

It is obvious that from the chain of equations c.-cMqM + cM taking into account the decreasing sequence C. the inequality C > 2C.+g follows. from This we get that a> 2T/g, where t is the number of equations in the chain, and that, thus, to find (o, b), we need to perform no more than 2log2o divisions with the remainder (log^x denotes the logarithm of the positive real number x on base 2, which is denoted Logx everywhere in this book).

Since dividing, as well as multiplying, two numbers that have a binary representation of length / bits, requires 0 (1G) elementary processor operations, finding the largest common divisor of numbers a and b requires 0 ((1od2a)3) operations. An elementary operation is an operation that is” atomic ” for a computer processor (for example, shifting a data string to the left by one bit, adding a zero bit to the right, adding two bits, and so on).

Here and below for two functions/(x) and d{x)> 0 defined in the domain D, we use the notation /(x) = 0(d(x)) if there is a constant K> 0 such that |/(x)| < Kgr(x) for all xeD.

Finally, we show that it is true that multiplying two numbers modulo n requires 0 ((log n)2) elementary operations. Indeed, multiplying” in a column ” two numbers that have 0(1od n) characters in the binary representation will be reduced first to performing 0 ((1od n) shifts to the left of the row representing the first co-factor of the product, and then to summing 0((log n) resulting from the shifts of the rows. The shift of the lines and their summation require 0((log p)d) elementary operations.

Another important result follows from the above chain of equations. From the upper equation of the chain, it is easy to Express the value of SG as a linear combination of values a and b and substitute it into the second equation of the chain. Then from the second equation of the chain, you can Express the value C2 as a linear combination of values a and b and substitute it into the third equation of the chain. As a result, going down to the last equation, we get that:

(,a,b)=xa+yb (A1)

for some integers x and y. Obviously, to find such a representation of the greatest common divisor of numbers a and b, 0 ((loga)3) operations.

Two integers o and b are called mutually Prime if (ar b) = 1. The fact that a and b are mutually Prime is also denoted by alb.

Two integers a and b are called comparable modulo a natural number t if their difference a-b is divisible by t without remainder. This is expressed by the following entry:

a = b (modm) (A2)

The number t is called the comparison module. If we fix the comparison module t, then any integer C can be uniquely represented as:

C = CT + g, (AZ)

where g is the remainder coinciding with one of the t numbers 0,…, t-1. The remainder of g is also called the subtraction of the number C modulo T.

We call all integers C that satisfy the equation (AZ) for a given g a class of deductions g modulo T. In other words,

g = {C :C = r (modm)}.

The set of all residue classes o, 1,…, (t-1) modulo t is denoted Zm.

If (o, t) = 1, then (A1) implies the existence of integers x and y such that 1 = XO+ut. Hence XA = 1 (modm). The number x is called the inverse of o modulo t and is denoted by o ” 1. The complexity of finding the inverse number is the same as that of the Euclid algorithm-0 ((log m)3). It also follows that the comparison az = b (modm) for {a, t) = 1 can be solved with respect to z in cubic time from the length of the binary representation t. To find z, first calculate the ATG, and then multiply it on the right by B. Any z of the form z = a ” 16 +”, where t is an arbitrary integer, is the solution of the equation under consideration.

Note that if (o, t) = 1, then (om1,rn) = l.

Let lit be mutually Prime positive integers. Then the system of equations

x = a (mod l) x = b (mod t)

has a unique solution x in the ZNM residue class.

The latter statement is called the Chinese remainder theorem. The proof of this theorem is given below.

From the first equation of the system follows x = Nn + a. Substituting this expression for x in the second equation, we get:

Ml = (b-a) (modm).

Since lit are mutually Prime numbers, there is an l “1 such that the equality Yal’1 si (modm) holds. From here we get:

N = (b-a)n~l (modm) or for some whole M:

N = {B-o) l“1 + Mm.

Substituting the last equality in the expression for x, we get: x = (B – l)l ” 1 + MTL + a, which was required to be proved.

A group is a non-empty set G of elements of arbitrary nature on which a binary operation is defined, usually called multiplication, for which the following properties are performed.

For any two elements a, beG, their product also belongs to G.

The associativity law is fulfilled: for all a,b,cegs (ab)c = a(b).

In the set G, there is a unit element e such that for any aeG, EA = OE = a is true.

For any os G, there is an inverse element a~leG, such that cggo = OO’1 = e.

A group G is called Abelian if the law of commutativity ab = ba holds for any a, beG. If a group consists of a finite number of elements, the number of elements of the group is called its order, and the group itself is called finite. If a subset H of group G itself forms a group with respect to an operation defined in G, then the subset H is called a subgroup of group G.

The following theorem holds.

For a subset of H to be a subgroup of g, it is necessary and sufficient that two conditions are met:

if x-Ray and /?2E / Y, then e N;

if he N, then /G1 e N .

The proof of necessity is elementary. If H is a subgroup, then H is a group relative to the operation defined in G. This necessarily requires the fulfillment of conditions (1) and (2).

Prove sufficiency. Let H be a subset of G and conditions (1) and (2) are satisfied. we Prove that H is a group. Indeed, let’s take some element of heH. Then it follows from condition (2) that /G1 6 N, and hence from condition (1) /g/G1 = EB N.

The associativity condition is easily proved. If hvh2,h3eH, then from the condition (1) follows (h1h2)hl 6 H and hl(hzh3) eH. In addition, due to the fact that simultaneously (h1hz)hi e G and h1(h2h3)e G, and in group G the associativity law holds, the equality holds

Let H be a subgroup of g and geG be an arbitrary element of g. The set of possible products gh, where heH, is called an adjacent class (more precisely, a left adjacent class) by the subgroup H, and the element g is its representative. An adjacent class with a representative g in subgroup H is denoted by DN.

Two results are valid for adjacent classes:

In the case of a finite subgroup H, the number of elements in any adjacent class is the same and coincides with the order of the subgroup.

Any two adjacent classes of DLN and D2n either coincide or have no common elements.

The first statement follows from the fact that if hlrh2eH and gh^ = gh2, then it immediately follows = h2.

Let’s prove the second statement. Let there be such hvh2eH that gj\l=glhv Then obviously for any heH grh = g2h2h~1hr i.e. DGN^D2H, and gzh = g1hlh2lh,r.e. D2H<^DGN. Thus, from the existence of a common element in two adjacency classes of the same group (DD = g2h2), it follows that these adjacency classes coincide (d1n = D2n). In the case where H and G are finite groups of orders t and g, respectively, the representation C = LM 7=1 takes place and it follows from the above proved statements for adjacent classes that g = TP. In other words, the following Lagrange theorem holds: The order of any subgroup of a finite group is a divisor of the group order. Consider the so-called cyclic subgroups that any group possesses. Every element of deb can be associated with a” generated ” cyclic subgroup, which is essentially the smallest of the subgroups containing element D. To define it, we introduce the concept of the degree of the element d. As usual, for any natural K, we define DC as the K-multiple product of d on itself. Next, we define d° = e, d~K = (DC)~1. When this degree is determined, the familiar rules for working with degrees apply: for any integer t \l n, the equalities dtdp = dt*p, (dt)p = DTP are fulfilled. It is obvious that if deb is an element of a finite group, then there is a natural / such that d‘ = e, and d ‘ Fe for /= 1, … / -1. The number / is called the order of the element d in group G. If DP = e is fulfilled for some n, then / / n (if n = kl+t, where l>t> O, then d‘ = eg, which contradicts the definition of the order of the element).

The degrees DX, DG,…, D1 = e form a cyclic subgroup Gg of order /, and the element d is called the subgroup generator. Indeed, the set of degrees d contains the unit D1 = E. For each element d ‘ e Gg, there is an element gl~] e Gg that is the inverse of it. Finally, a multiplication operation is performed, the law of associativity and the multiplication operation is closed in G: for any natural t and p, not exceeding one order / run equality dtdp = dt+n = D5 e Gg, where 0 < s < / — remainder of division t+n /. Since Gg is a subgroup of G, by Lagrange’s theorem I \ n, where p is the order of the group G. It may happen that for some element d, the cyclic subgroup generated by it coincides with the entire group G. In this case, the group G is called cyclic, and the element d is called the group — forming element. It follows from Lagrange’s theorem that if the order of a group G is a Prime number, then the group is cyclic, and every element of the group, with the exception of the unit element e, forms it. Such a group contains only two subgroups: G itself and {e}. The Euler function f (/?), l>1 is defined as the number of natural numbers a < p, such that (a, p) = 1. If p = p, where p is a Prime number, then f(p) = p-1. If n = pm, where p is a Prime number, then f(pm) = pm-pm_1. Let’s prove the last equality. It is obvious that the number a<RT is not mutually Prime with RT if and only if a = gr for some whole 1<g<RT~g-Then the number of numbers mutually Prime with RT is equal to RT-1 – (RTO 1 — 1) = RT-RTL, which was required to prove.

For the Euler function, the following important statement is made, which allows calculating the value of the function for any natural p. If (t, p) = 1, then (p(TP) = f (t) f(l).

Indeed, (x, TP) = 1 if and only if simultaneously (x, t) = 1 and {x, p) = 1. Let a \l b be the remainder of the division of x by type, respectively. Then comparisons are made:

x = a (mod p) x = b (modm)

Obviously, from (x, p) = 1 and (x, t) = 1 follows (a, p) = 1 and (b, t) = 1. On the contrary, let (a, p) = 1 and (b, t) = 1 for some pair a <p and b < t. Then, according to the Chinese remainder theorem, in the residue class 1T, there is a unique solution x that satisfies the comparison system (A4). In addition, by virtue of (o, l) = 1 and (b, t) = 1, (x, TP) = 1 is fulfilled.

Thus, we proved that for any x<TP such that (x, TP) = 1, there exists a unique pair a<p and B<t, such that (a, l) = 1 and (b, t) = 1. In addition, the converse is also true: for any pair a < l and b < t such that (o, l) = 1 and (6, l?) = 1, there is a unique non-negative x<TP such that (x, TP) = 1. Hence the statement f(LT) = f(l?)f(l) for (t,p) = 1.

For some natural l, consider the set (Y(l) of natural numbers a<p, mutually Prime with l. The usual multiplication modulo l is considered as a binary operation defined on U(n). We show that U(n) is a group of order f(l). Obviously, the unit of the group is the number 1. further, As shown above, for any a < l that is mutually Prime with l, there is a number SG1 < l such that aa~l = 1 (mod l) and a~l&U(n). Finally, the associativity of the operation follows from the associativity of multiplication.

Let’s take an arbitrary number AE (Y(l).Let its order be /, i.e. a[ = 1 (modl). Since the elements a’ (modl) when /= 1,…, / form a subgroup U(n), it follows from Lagrange’s theorem that /|f(l). But then for any LEU/(l), AF(l) = 1 (p^l) is true.

If we now consider any positive integer C that is mutually Prime with l, then it is obvious that c = b{mod l) for some integer be U(n). Then the equality SF(p) ^BF(p) =1 (mod l) is fulfilled . In other words, we proved Euler’s Theorem:

if (C, l) = 1, then C<p(l) = 1 (mod l).

It follows from Euler’s theorem that if l is a Prime number that does not divide with, then SP~1 = 1 (mod l). This result is called Fermat’s small theorem and is widely used in cryptography.

Let’s continue a brief excursion into algebra and introduce the concept of a ring. A ring is a non-empty set K on which two operations are defined, conditionally called addition and multiplication, which have the following properties.

The set K forms a commutative group with respect to the addition operation.

Multiplication is associative, that is,for any a,B, s true (ab) c = a (BS).

Addition and multiplication obey the distributive law, i.e. for any a,B,C&K, the equalities (a + b)c = AC+ BC and C(a + b) = CA + cb are fulfilled.

In this case, the set K, considered only with respect to the addition operation, is called the additive group of the ring.

Important examples of rings are the set of integers with addition and multiplication operations, and the set of residue classes modulo p. The General definition of a ring does not require multiplication to be commutative. In that case, if the multiplication has the additional property that the ring is called commutative.

Multiplication in a ring, as in a group, is an associative operation, but other properties of group multiplication in a ring may not be performed. However, the most important in practice, the rings contain a single element with respect to multiplication. But even such rings contain elements for which there is no inverse (irreversible elements). In any ring, element 0 is irreversible— the unit element of the additive group of the ring. Non-zero elements of the ring can also be irreversible.

A commutative ring with one in which every nonzero element is invertible is called a field. Due to this definition, the set of non-zero field elements forms a commutative group with respect to multiplication, which is called the multiplicative group of the field.

It is easy to prove that the residue ring modulo a Prime number p is a field that is called the residue field modulo p.

In algebra, we prove that in an arbitrary finite field, the number of elements q is always a power of a Prime number: q = pn. The converse is also true: for any q that is a power of a Prime number, there is a field with q elements.

The final fields are called Galois fields and denote GF{q). An important property of finite fields used in cryptography and coding theory is that the multiplicative group of a Galois field is a cyclic group of order q-1. The forming element of the multiplicative group of the Galois field is called the primitive element of the field.

To illustrate the above, we prove that the multiplicative group of the residue field modulo a Prime number p is cyclic. We also describe an algorithm for finding all the generators of this multiplicative group.

First, we prove the following Lemma.

Lemma 1. If in an Abelian group G there are two elements of orders g and s, then in the group there is an element whose order is equal to the smallest common multiple of g and s.

Denote by o and ft the elements of group G of orders g and 5, respectively. Decompose the orders g and 5 into Prime factors:

r=Pi’ x…XP£ ‘ and s = p {‘x…xp[k,

where pv…, pk are different primes.

Without limiting generality, the Prime factors in the representation g and s are written in such an order that for some 1 <t<K, the inequalities are met:

— L’e2 — /g’ – fm And 6sh+1 ^ / t+1 ‘ EC < fk *

Denote G0= reg ‘ x…hrett and 50 = p£% x…HR[K.

Obviously, (G0, 50) = 1. Next, we denote r=rQry 5 = 5051 and C = ahbs’. Let p be the order of element C, i.e.

SP = e (A5)

Obviously, cwb _e, i.e. l | g050. Let’s raise both parts of equality (A5) to the power rQ:

cr°n = AV’nbs’r°n = e

Note that the resulting representation is valid only if the multiplication operation in the group is commutative.

Since =e, we get B5LP =e, which means s0 \r0n. Since (V s0) = 1, it follows that sQ | p.

Similarly, by raising both parts of the equality (A4) to the power of 5^ we can prove that r01 n. Given n|, we get that n = r0s0. Thus, the statement of Lemma 1 is proved.

Let us now prove Lemma 2: Let f(x) be a polynomial of degree K with integer coefficients and a higher coefficient (coefficient for a*) 1. If p is a Prime number, then f(x) has at most K roots in the ring 1P. We prove the Lemma by induction on the degree of the polynomial t. If t = 1, then j\x)=x+b and the corresponding equation has only one solution-B in Zj, i.e. the Lemma is true. Let us now assume that any polynomial of degree K-1 with the highest coefficient 1 has at most K-1 roots in Zp. We show that this assumption implies a similar statement for a polynomial of degree K with a higher coefficient of 1. Let/(x) be a polynomial of degree K with the highest coefficient 1. If/(x) has no roots in Z^ then the statement is proved. Let/(x) still have the root aeZp, i.e. /(a) = 0 (mod p) (here a is a representative of the residue class a). Then, obviously, there is a representation of /(x): /(x) = (x – a)p (x) + /(a), where the power q(x) is equal to K-1. The last equality is equivalent to: /(x) = (x-a)p(x) (modp). Let p^AE Zp be another root/(x) in Zp (if there is no such root, the Lemma statement is proved). This means that /(P) = 0(mod p), but P?td(mod p). Substituting b (AB) P instead of x, we get: ° = /(P)g (R””LR) (mod P)- Since p is a Prime number, it follows from the last equation that g(P) = 0(mod p). In other words, from the fact that p is the root of a polynomial other than a, it follows that p is also the root of the polynomial p(x) in Z. It follows that in Zp, the function /(x) can only have one more root than p(x). And since, under the assumption of induction, q(x) has at most K-1 roots in Z, the polynomial /(x) has at most K roots in Zp, which was required to be proved. We now denote by U(p) — the set of all nonzero residues modulo R. Then the primitive roots theorem holds: If p is a Prime number, then U(p) is a cyclic group. Take an element al^U{p) of order kv If ^ = p-1, then the statement of the theorem is proved. If kg < p-1, then AG e U{p) satisfies the equation x*1 -1 = 0 in Zp. Since p is a Prime number, Lemma 2 implies that the equation xk’ -1 = 0 has no more than kg of roots in Zp. On the other hand, all elements of the set H = {1, a1,aiz,…, a1k^1} are different and are the roots of the equation x*1 -1 = 0 in Zp.

Since, by assumption, K1K1.

Further, if K2 = p-1, the resulting element is a constituent of the group U(p). Otherwise, everything is repeated with the constructed element of order kg. It is obvious that due to the upper bound of the sequence K. after a finite number of steps, an element of the group of order p-1 will be found, which is the constituent of the group U(p).

Let geU(p) be the forming element of the group U(p), and let I be a number that is mutually Prime with p — 1. Then D1 is also the forming element of the group U (p). Let s be the order of the element D1, i.e. D15 = 1.Since p— 1 is the order of the element d, the relation (p – l)|/s holds. Since by construction ((p-1),/) = 1, it follows (p-l)|s. On the other hand, the equality GL(p-v = 1) holds. It follows that s = p-l, i.e. the order of the element D1 is equal to p-1, which means that D1 is the forming element of the group U (p).

It follows from the above proof that the group U(p) contains f(p -1) of various generators.

Consider some simple p > 2. If for oeGF (p) there exists an element Xe GF (p) such that a = x2 (mod p), then a is called a quadratic deduction modulo p. Otherwise, when the equation a = XG (mod p) has no solutions, and is called a quadratic non-unit modulo p.

The above definition of a quadratic deduction can still be formulated as follows. If g is the generating element of the multiplicative group of the field GF(p), then a is called a quadratic subtraction modulo p, if a = g2k (modp) for some natural K. If for aeGF(p) for some natural K, o = p2/r+1 (modp) is satisfied, then a is called a quadratic non-quotation modulo p. Indeed, in this case it is impossible to find such Xe GF (p) that a = XG (mod p), because if such x existed, then the equality a = DG (modp) would immediately follow for some K. Thus, there are only (p -1)/2 quadratic deductions and non-deductions.

The Legendre symbol in the case of an integer a and a simple p> 2 is defined by the equality:

O, if p|a,

H^Y

= j 1, if a is a quadratic deduction modulo p -1, if a is a quadratic deduction modulo p.

It is clear that a can be replaced by any integer comparable to o modulo p.

Thu

_ (t-1)/g

=0 (modm)

(A7)

We prove the following result: if t is a Prime number, then the equality holds for all a:

If t | o, then the equality (A7) is obvious. If a is a quadratic subtraction modulo t, then the left part of the equality (A7) is equal to 1 and, in addition, a can be represented as a = g2k(modm) for some natural k. With this in mind, the right side of equality (A7) takes the form gkTl) (modm) and by virtue of Fermat’s small theorem gk(m-i) *i (mod). Thus (A7) is proved. If a is a non-quadratic subtraction modulo Tg then the left part (A7) is -1 and, in addition, a can be represented as a = g2k+l (modm) for some natural K. With this in mind,the right part (A7) takes the form gk(m-v+(m~v, z and By virtue of Fermat’s small theorem DKG-1)NT-1)12 =d{t-C/2 (modm). From Fermat’s small theorem follows the equality: (d(t-1) p + i)/z* !) = o (modm).

Since the second factor of the last equality cannot be compared to zero modulo t, since t-1 is the order of the generating element d, we get that

d(t-i)/2s-a (modm).

The Jacobi symbol is a generalization of the Legendre symbol to the case of an arbitrary odd number. Consider an integer a and an odd t>2. Let m-p’i x…x^ be the Prime factorization of t. Then the Jacobi symbol is defined as the product of the corresponding powers of Legendre symbols:

We prove the following theorem: if t is an odd composite number, then no more than half of the integers a, where (a, t) = 1 and 1 < a < t, satisfy the condition (A7), in which the transformation on the left side of the comparison is now understood as a Jacobi symbol. First, we construct a such that (A7) does not hold for a = a. Depending on the representation t = p[‘ x’…HR[K consider two cases. Let us prove that (SL = 1. Indeed, K ( Yj a P 7=1 (A8) Case 1. Let’s assume that among iv…, ik there is a degree whose value is strictly greater than 1. Without generality restriction, we will consider \ >2. Then let’s put a = 1 + t / RG.

Since for all j=l,…,k by definition, and compares a = 1 (modp;), then from (A7) it follows that each factor on the right of (A8) is equal to 1, where

On the other hand

Since RG does not divide – – -, we get that 2 p does not

it is divided entirely by t, i.e. a(t-1)/2 F1 (MoDT), which means that the equality (A7) for the constructed element a is incorrect.

Case 2. The equality ^ =… =ik = 1 is fulfilled, i.e. t=RG x…HRK. Let s be an arbitrary quadratic non-integer modulo, and let us Construct an element a such that it simultaneously satisfies two comparisons:

a = s(modpa) and a = 1 (modm/p^).

Since the modules of the above comparisons are mutually Prime numbers, in accordance with the Chinese remainder theorem, there is a unique element a that satisfies these comparisons up to a comparison modulo t.

It is obvious that from the comparison a = l (modp7) by virtue of (A7) follows = 1 for all j=2,…, k. Then by virtue of a = s (modp1) has

From the comparison a^Hmodm/pj), it follows that a = l (modp;) for all j = 2,…, K. it is Easy to see that

If there were equality (A7), then the result would show that a (m“1)/2 = -1 (modm), i.e. there would be an integer With such that

a (t-1)/2 = C]”[P7 -1.

7=1

Since a = l(MoDT/RG) holds, the relation a(m-i)/2 (mod/77/pj) is true, i.e. there exists a such That

a{t-g)/g=A[1P] + 1.

7=2

This means that

CR no. – L> = g.

7=2

which is not true for any integer values of A and C. Therefore, the assumption a(m“1>/2 = -1 (modm) is incorrect.

Thus, for any composite number t, a was constructed such that the equality (A7) for o = a does not hold.

Consider now all integers 1<co, <t, (co,, t) = 1, 1</<£, satisfying (A7). Then, obviously, all numbers of the form

The latter property is called the law of reciprocity. It allows you to significantly simplify the procedure for calculating the Jacobi symbol and is widely used in the Solovey-Strassen method of checking the number for simplicity