 Int. J. Communications, Network and System Sciences, 2011, 4, 287-296 doi:10.4236/ijcns.2011.45033 Published Online May 2011 (http://www.SciRP.org/journal/ijcns) Copyright © 2011 SciRes. IJCNS Protection of Sensitive Messages Based on Quadratic Roots of Gaussians: Groups with Complex Modulus* Boris Verkhovsky Computer Science Department, New Jersey Institute of Technology, University Heights, Newark, USA E-mail: verb73@gmail.com Received April 5, 2011; revised May 3, 2011; accepted May 20, 2011 Abstract This paper considers three algorithms for the extraction of square roots of complex integers {called Gaus- sians} using arithmetic based on complex modulus p + iq. These algorithms are almost twice as fast as the analogous algorithms extracting square roots of either real or complex integers in arithmetic based on modulus p, where p is a real prime. A cryptographic system based on these algorithms is provided in this paper. A procedure reducing the computational complexity is described as well. Main results are explained in several numeric illustrations. Keywords: Complex Modulus; Computational Efficiency; Cryptographic Algorithm; Digital Isotopes; Multiplicative Control Parameter; Octadic Roots, Quartic Roots, Rabin Algorithm, Reduction of Complexity, Resolventa, Secure Communication, Square Roots 1. Introduction and Problem Statement The concept of complex modulus was introduced by C. F. Gauss . The set of complex integers is an infinite sys- tem of equidistant points located on parallel straight lines, such that the infinite plane is decomposable into infi- nitely many squares. Analogously, every integer that is divisible by a complex integer m = a + bi forms infini- tely many squares, with sides equal to 22ab. 1.1. Complex Moduli Let’s denote . Associates of ,:aba bi:,Gpq are –G, iG and –iG; they are the vertices of a square where ; ,Gpq 0, 1,p q,q piG, ,p qqp ; . 0, 1iGTo understand the congruencies, let’s consider a sys- tem of integer Cartesian coordinates. The squares on this system of coordinates are inclined to the former squares if neither of integers a, b is equal to zero . Then the associates of the modulus are rotations of “vec-tor” on 90 degrees. Let’s consider the plane of complex numbers and as an example, the complex prime number . Let the left-most bottom point of the mesh be the origin of the coordinate system for Gaussians, and let be the Gaussian modulus. Inside each square there is a number of Gaus-sian integers; plus every vertex of each square is also a Gaussian integer. In order to avoid multiple counting of the same vertex, we consider that only the left-most bot-tom vertex of each square belongs to that square . For more insights and graphics see . ,pq,,pq1,4 :14i:1 41,4Gi  2,,modThis paper is a logical continuation of a recently pub- lished paper , which considered a cryptographic scheme based on complex integers modulo real semi-prime pq. The above mentioned paper describes an extractor of quadratic roots from complex integers called Gaussians. A slightly different approach is considered in . Several general ideas for computation of a square root in modular arithmetic are provided in [5-7]. This paper considers arithmetic based on complex in- tegers with Gaussian modulus. As demonstrated below, the extraction of square roots in such arithmetic requires a smaller number of basic operations. As a result, the described cryptographic system is almost twice faster than the analogous systems in [3,4]. Consider quadratic equation xycdpq, (1) where modulus :,Gpq is a Gaussian prime; and let 2:,Npqpq2. (2) *Dedicated to the memory of Samuel A. Verkhovsky. B. VERKHOVSKY 288 1.2. General Properties Proposition 1: Gaussian is a prime if and only if its norm N is a real prime . ,pqRemark 1: Since ,,pq qp , without loss of generality we assume that, if is prime, then p is odd and q is even {unless it is stated otherwise}. ,pqProposition 2: If norm of ,pq is a prime (2), then for every  ,, 14pq N is an integer. Proof: Let and . Then (2) implies that :2 1pk :2qrr214 1Nkk . Q.E.D. (3) Proposition 3 {cyclic identity}: If gcd,,,1, 0abpq  and G is a prime, then the following identity holds:  1,mod,1,Nab pq0d. (4) Remark 2: More details about identity (4) are provided in the Appendix in Proposition 3.A. Proposition 4 {Modular multiplicative inverse}: if , then gcd, ,,1,0abpq  12,,moNab abG. (5) Remark 3: Yet, more computationally-efficient is to solve an appropriate Diophantine equation. However, this is beyond the scope of this paper. Definition 1: Gaussian ,xy is called a quadratic root of modulo G if ,cd,xy and  satisfy Equation (1); we denote it as ,cd ,: ,modxycdG. (6) 2. Quadratic Root Extraction Where 5mod8N Proposition 5: If ,pq is prime and 5mod8N, then :14moqmN is odd. Proof: Notice that d 42, otherwise (3) implies that . Q.E.D. 1mod8N 2.1. Quadratic and Quartic Roots of 1, 0 Modulo ,pq Consider a quadratic root ,uw of mo1, 0d,pq:  ,: 1,0mod,uw pq, ThiGo (7) Since the last equation does notlu. Then ,uw s equation holds if either w = 0 and 2ur if u = 0 and  222,21,0moduw uwpq .1mod; 21modGw  . have a real integer so- tion for w, it implies that  ,0, modp qG,1,01uw  . (8) Hence, if a root ,xy is known, then another root of ,d is c,yThere ar, d.uw xG mooots: e Qu1, 0, artic rfour quartic roots of each satisfying 41,0kq: (1,0);qq q123 4(1,0);0,1;0,1 ;q  (9) where 223,4 22 1mod; 1,0mod.qq GqqG  .2. Quadratic Root Extractor (QRE-1) Step 1.1: Compute 2 22:; Nmpq :14; 38NzN (10) Step 2.1: if N is not a prime, then QRE-1 algornoithm is t applicable, na ; Remark 4: 1,1, 0modpq G; (11) Step 3.1: Compute (12) Step 4.1: if modmcd G;:,E0, 1E, due (GQNRthen dr 5.1: if ,cdits squ is Gaussian qua- atic non-resi}, i.e. are root does not exist; Step1, 0E, then  38mNx,: ,odyc G; (13) Step 6.1: if d1, 0E , then 1:0,1 mod;mod REGGR ; (14)  ,:,modzxyRcd G ;nd (15) Step 7.1 {2 square root}: ,:1,,tvpqxymodG (11). (16) .3. Validation of Algorithm Proposition 6: Suppose 2 a) ,pq is a prime and 2mod4q; (17) b)  1438; md :,oNEcd GzN  ; (18) c)  1 if 1,mod0 or 1,0REEG; (19) then  ,,mozcd RcdG.d (20) Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY289 Proof: First of all, (19) implies that (21) Yet, 2mod1, 0ERG . 34 14222,, , ,modNNR cdcdR cdERcd G.(22) Therefore, (21) and (22) imply equation  (23) which itself implies that (20) is correct. Q.E. has a quadratic root odulo Gaussian prime ly if ,cd ,,modcd RcdG22z,D. 3. Criterion of Gaussian Quadratic Residuosity Where 5mod8N Proposition 7: Gaussian ,cd ,pq onm14,md1,0Ncd G . (24) oExample 1: Consider ,8317,pq es. 91,6; Npqwhich is a prime; hence are Gaussian primC91, 6 ompute  : 1mNLet  ,81,71cd . S4/2079; :ince 38 1040zN ; 81,71 m 96,85 1,0mod 91,6  (11), therefore,  0,1 (25) ,81,71 81,71 57,75mod91,6.xy  Verification: Indeed, . (26) 4. Numeric Illustration N = 109; m = 27; z = 14. In Table 1 are the quartic roots of unity 104057,75 m2od 91,681,71 Consider p = 10, q = −3. Then m,cd k(9), i.e., q 1:1,012,71,0;3,90,1 ;q q 2 34; 10,20,1mod,R qqpq . Step-by-step process of extraction of the square rooand criteria of quadratic residuosity are illustrated for sets veral values of ,cd . 5. Quadratic RExoot traction (QRE-2) 5.1. Basic Properties and Where 9mod 16N Proposit ion 8: if 3pmod80mod4q, then able 1. Quadratic root extraction and verification; Tmod 8 = 5 . N,cd (3, 8)(4, 8) (6, 7) (8, −2) (9, 2)(10, 5),mcd (1, 0) (10, −2) (−1, 0) (−1, 0) (3, 9)(1, 0),zcd (9, −2) QNR (5, 3) (11, 4) QNR (2, 2),zcd R(9, −2) na (7, 2) (7, −1) na (2, 2)2,xy (3, 8) *** (6, 7) (8, −2) *** (10, 5) :1mN 8is odd and 716N is an integer. Proof Si = + 3 and he : nce p 8w q =4r, terefor2216 439Nwwr  (2). Hence 16 7N. If we assume that m is even; then 7 7) 1612Nm. (2Thus, if 2m is integer, then 716N is not (27). This contradiction proves Proposition 8Proposition 9 {criterion of Gaussianos. quadratic residu- ity}: Let 18:, modNEcd G; (28) and gcd, ,1cdG. Then ,cd if has a quadratic roote G modulo Gaussian prim,0;0:1 ,11;iE; {see the algorithm below}. (29) Proposition 10: Suppose a) p is odd and 0mod4q; (30) b) 716zN ; (31) satisfies the fc) Resolventa Rollowing conditions:   31,0mod if 1,0; (32)GE0,1mod if 1,0; (RGE 33)mod if 0,1; (34)EGE Then  ,,mozcd RcdG.d (35) in (32)-(34) Proof: Notice that 1modRE G. s that If (35) is correct, then it implied (36)  ,,cd Rcd22mozG.On the other hand,  odG; (37) 21822,,,mzNcd Rcd cdRth ply that erefore (28), (32)-(34) imCopyright © 2011 SciRes. IJCNS B. VERKHOVSKY 290 ords, it confirms as- 5.2mod ,1ERp q. (38) Hence (36) is correct. In other wsumption (35). Q.E.D. 2. Octadic Roots of 1,0 Modulo ,pq onsider roots of 8th poCwer (called the octadic roots) of roots: 8 unity; there are eight suchfor k = 1, ···,  81,23,45,6 7,8:1,0: 1,0;:0,1; :0,1;:0,1keeeee  (39) Then 2ee. (40) Therefore, the resolventa R must satisfy the following equations for k = 1, 2, ···, 8: . (41) if3,4an(43) 5.3. Computation of  22213,4225,637,841, 0;1, 0;0,1;0,1eeeeee  1mod1,0 or modkkReGR eGThus, 1: if 1,2kkRe ek ; 132: kkkkkReeeeek ; (42) d 17422 0,1 if:0,1 if 7,8kkk kkkkkkeR eeeeeeeek 5,6 k. 0,1i Modulo ,pq If is fixed and , then this root Direct computation: Since ,pq mod 169Nadvance. must be pre-computed incos π2sinπ2ii cosπ4sinπi41,122, it is necessary to compute square root of two and multi- plicative inverse of two modulo G. 5.4. Multiplicative Inverse of 2 Modulo ,pq f p is odd and q is even, then I1212,2mod,pq pq ; if q is odd and p is even, then 1212,2mod,qp pq . Otherwise the modular inverse of 2 does not exist. then Example 2: Let G = (8, −3);122,4mod8,3 and 25,1mod8,3. Hence  1, 15, 12,42,3mod8,3i [8deed,  ]. In82,31,0mod8,3. Indirect computation: In general, observe that if square root of 2 does notnd for a Gaussian exist a ,abhouality lds ineq,mod1,;0,1ab G18N: 0F , (44) then 18,mod or NabG ii. (45) Although in this case we do not directly compute 0,1mod G, it is obvious that if 2mod 0,1FG (44), then  0,1 modiFG ; (46) otherwise 0, 10, 0, 11modiFG . (47) for Quadratic Root Extraction Step 1.2: 5.5. Algorithm 22:; :18; 716mNNp Nqz  (48) Step 2.2: if N is not a prime, then the QRE-2 algo- rit plicable; Step 3.2: Find a Gaussian for which hm is not ap,ab,:, mod1,0;0,1Fab G; (49) Step 4.2: if m,20,1Fm:oRF iG then d; if 20,1F, then m:0 odRFiG,1; ( Step 6.2: ifStep 5.2: Compute :, modmEcd G; 50)  1, 0;0,1E (22), then square root of ,cd does not exist; E = (1,0), then ,: ,modzStep 7.2: ifxycdG; goto Step 10.2; Step 8.2: if 1, 0E , then  ,: mo0d,1z,xyc G; goto Step 10.2; dStep 9.2: if 0,1E, then ,: ,0,1 modRzxycdG;  goto Step 10.2; (51) else (52) Step 10.2 {2nd square root}: ,: modxy G;,zcd R,:1,,modtvpq xyG . (53) Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY Copyright © 2011 SciRes. IJCNS 2916. Second Numeric Illustration C= 73, i.e., 41,0mod, 1,2,3,4.jqGj (56) onsider  ,8,3pq, then N Definition 4: is a octadic root of if ke1, 0739mod16; 9; 5;mz (54) 81,0mod, 1,2,,8.keGk (57) Octadic roots of 1, 0: Definition 5: ls is a sedonic root of if 1, 02110,51,0;e 16 1,0mod, 1,2,,16.lsGl (58) 2 10,51,0mod8,3e; 7.2. Resolventa of Quadratic Root Extractor 238,2; e 10, 58,20,1;  Proposition 12: Suppose  243,710,5; 3,70,1e; a) 7mod16 and 0mod8pq, (59)  252,38,2; 2,30,1e ; b) 22:; 1532; :116Lc dzmNN (60)  269,28,2; 9,20,1e; c) Let ; and resolventa R satis-fies the following conditions:  :, mod,mEcd pq 275,13,7; 5,10,1e; 1:mod if iiRuu GEu;i (61)  286,63,7; 6,60,1e. The following nine values of 13:mod if j;jjRqq GEq  (62) ,cdrithm. in Table 2 illus-trate various cases of QRE-2 algo 7. Quadratic Root Extraction (QRE-3) .1. Basic Property and Roots of Where 17mod 32N 17:mod if kkkRee GEe  ; (63) 115:mod if llRs s GEs  ;l (64) then  ,,mozcd RcdGd. (65) 1, 0 7 Proposition 11: Anroved th7 mod8Proof: Let alogously it can be pat if  and , then,, ,:mzodxycdRcdG . (66) 16p0modq 15 32N is integer and 6:11mN is odd. ; then i.e., Therefore Proof: Let 16 7pk and 8qr  15 1622,,NcdRcd ERGmod. (67) 32872 49Nkk, 32 15N. If iEu, then Notice that 15 322 . On the other hand, if m is even, en 1Nmth12m is not an inte imger, which2221, 0modiERE uG; (68) 15 32N plies that is noteger. Q.EDefinition q ua re r1, 0 if an int.D. 2: is a sot of iu oif jEq, then  21,0mod, 1,2ii2441, 0modjER E qG; (69) .uG (55) Definition 3: is ic root of 1, 0 if if kEe, then a quartjq Quadoot extractor where 9mod 16N. Table 2.ratic r,cd (1, 1) (3, −1) (5, 1) (5, 5) (7, −1) (8, 5) (10, 3) (3, 4) (4, 3) ,mcd (2, 3) (0, 1) ) (0, −1(0, −1)(1, 0) (0, 1) (9, 2) (8, −2) (−1, 0) ,zcd na ((8, 1) 8, 5) (3, 6) (5, 7) (1, 2) na (3, −1) (9, 19) ,zcd Rna (4, 5) (9, 4) (4, 1) (1, 2) (5, 4) na (2, 2) (7, 6) 2,xy na (3, −1) (3, 4) (4, 3) (5, 1) (5, 5) na (8, 5) (10, 3) 58,,Ee eNB1: If , then QRE-2 algorithm is not applicable, since the square roots of do not exist. 58,,ee B. VERKHOVSKY 292 1, 0; 288 modkRE eGE (if , the ( .3onic Roots of 70) lEsn 1, 021616 molER EsdG. 71) 7. Sed1, 0 Modulo G ity wo square rootsUn 0 has t1, 1, 0and1, 0; 0,1; 0,fouroots ctadi quartic rc roots  1,0; 1,0; 1; eight o 5678; 0,1;,,,eeee1,0;1,0; 0,1 and sixteen sedonic roots  5678910 15161 ,,,,es s, 1, 0;1, 0;0,1;0,,,,,,eeess where   5,6 0,1 ,e 7,813,14,15,16 0,1 and 0,1.es   (72) d Numeric Illustration Consider N = 113; 7. Then 9,10,11,12 0,1 ,s7.4. Thir,8,pq :1167; mN :1zNw 5324. In Table 3 belo; 1,014, 1 0,18,6 ;  0, 1(7,7)mod8, 7 ; 6,5 ; 0,10, 19,4; 0,13,1 ;  0 mo,112, 2d8,7 ; 10,5;12, 2;10, 2;5, 2mod8,; (73) 0, 1 70, 15, 4;3,3;5,3;10,3mod8, 7 . (74) In (74) there are four sedonic roots of (1,0) thatbe pre-computed on the design stage of the QRE-3 algo- rithm. Although this is a non-deterministic process, each of these roots must be computed only once priorthctose roots crresp must to using e extrar. Theoond to  mod, 1,0mgh G, w = 716:Ehere m; ,8,pqG 7 and Gaussians  6 4. ,: ;10,1;11gh ,3 ,3;5,The remaining four sedonic roots liequivalent to negative values of roots in (7sted in (73) are 4): 10,55, 4;12,23,3;1,25,3;5,21 0,30  .  Step 1.3 {System design}: Every user (Alice, Bob,…) selects a pair of Gaussian primes and 8. Cryptographic Algorithm ,pqrs, as his private keys, and computher/es ,qrs22q, :,npNpes as m, Step 2.3 {Generalized Chinese remainder Theorem m.her/his public key; she/he pre-computz and R; odulo composite Gaussian n}: Each user pre-computes his/her parameters of CRT:  11:,mod,; :,m od,MpqrsWrs75) Step 3pq (.3 {Encryption by sender (Alice)}: Alice repre-sents the plaintext as an array of Gaussians and inserts digital isotopes into every Gaussian ,ab ; Step 4.3: Using Bob’s public keye computes ci-phertext roots of C mod n, sh2:,modCab n; (76) and transmits C to receiver (Bob) via open channels of a communication network; Step 5.3 {Decryption by receiver (Bob)}: He com-putes square,pq and mod ,rs , where ,pq and ,rs he CRTare Bob’s pd his pre-comrivate keys; Step 6.Using t an Table 3. Binary tree of sedonic roots of 3: puted M andW (75), Bob computes all quadratic roots of ciphertext C; Step 7.3: Bob recovers the initial plaintext {by select- 1, 0 where modulus 8, 7G. ,gh (6, 3) * (10, 1) * * (11, 3) * (5, 4) * 16 1, 0E (5, −4) (10, 5) (3, 3) (12, −2) * (5, 3) (10, −2) (10, 3) (5, −2) 281, 0E * (6, 5) (9, −4) * * * (3, −1) (12, 2) * 441,0E * * (7, 7) * * * (8, −6) * * 81, 0E * * * * (−1, 0) * * * * * * * * (1, 0) * * * * 16E NB2: For the sake of brevity, only 1/2 of all roots are listed in every row of Table 3; all remaining roots are listed in the rows below. For instance,     81,06,5;9,4;3,1;12,2; and 7,7;8,6; and 1,0; and 1,0. Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY293 Table 4. Residuespplicaare rooxtractornd exams of coding NN mod 32 59 13 , able squt es aplerrespon. 17 21 25 29 QRE QR E-2 QRE-1 Q E-1 QRE-2 QREE-1 QR RE-3 QR-1 N1260773 692969 432589 386641 612373 525913 906557 5, 496) (113, 498) (212, 805) (258, 605) (37 (522, 583) (157, 708) (421, 854) N2 750077 (35130) (16,9) (274) (469) (179) (485) (116) ,pq 812101 249257 360781 676337 159157 405529 ,pq , 8 495, 534, 674, 35, 63, 86 ing the quratic rootat has sotopeThis algorithm is a gn crypgraphic algothm [h eme sqalgorithmr encrypecryf real modulo semi-prime , where are primes. . Reduction of Computational Complexity ad of C theneralizatiodigital i of the Rabins }. to- ri10], whicploys thuare root fotion and dnpqption op and q integers 9 In Step 3.1 (12) and Step 4.1 (13), two exponentiations are performed to compute ,cd to the powers m an d z respectively; these operations are the most time-con- suming. However, observeere is a simple linear rela- that thtionship between m and z: 21 154zm N . (77) This implies that it is sufficient to execute only one exponentiation. Indeed, we initially compute 11:, modzAcd G; {one exponentiation}; (78) then 12122mod:,zAA cdG ; {onenally squaring}; (79) after that 32:,,mAA cdcd ; {one multiplication}; (80) and fi41:,,zAA cdcd  ; {one multiplica-tion}. icability of QRE Algorithms Consider , who integer squares. For such N his paper tion of (81) 10. Appl:mod 32ANbe represented as a sum of twAere N are primes, which can the residues are equal 21,25 and29Table 4 above indicates which algorithm is applicable r each value of residue A. :1,5,9, 13, 17,. foTherefore, the three algorithms provided in tover all cases of prime moduli with the excepcod32Ncase can still be covprim1m . Yet, eredmost moduli latter if we coner QR rithms, of the sid in theE algowhere the es od 64; 33Nm128N; the als de-65 modageneralnd in d , for integer 5t gorithmes wherescribeabove can be generalized for the cas  t,1mod2t21N (82) en component and the ev in the corresponding modulus ,pq is divisible by 12t. 11. Conclusion and Acknowledgements Thd andy ncryption/ecrtion protocol based I appreciate S. Medicherla, S. Sadinonynd typesetter for their sugges--ree algorithms which extract square roots of Gaussians in arithmetic, based on Gaussian modulo reduction, are considere analyzed in this paper. Several numeric illustrations provide further explanation of these algo- rithms. A public keedyp on this arithmetic is described in the paper. This crypto- graphic protocol is almost twice as fast as the analogousprotocols published by the author of this paper in [3,4].k and B. Saraswat for assistance in numeric illustrations and my gratitude to J. Joes, A. Koval, M. Linderman, R. Rubino and mous reviewers atheantions that improved this paper. 12. References  C. F. Gauss, “Theoria Residuorum Biquadraticorum,” 2nd Edition, Chelsea, New York, 1965, pp. 534-586.  M. Kirsch, “Tutorial on Gaussian Arithmetic Based on Complex Modulus,” 2008. http://wlym.com/~animations/ceres/index.html  B. Verkhovsky, “Information Protection Based on Ex-traction of Square Roots of Gaussian Integers,” International Journal of Communications, Network and System Sciences, Vol. 4, No. 3, 2011, pp. 133-138. doi:10.4236/ijcns.2011.43016  B. Verkhovsky and A. Koval, “Cryptosystem Based on Extraction of Square Roots oLatifi, Ed., Proceedings of 5f Complex Integers,” In: S. th International Conference : New Generations, Las Vegas, on Information TechnologyCopyright © 2011 SciRes. IJCNS B. VERKHOVSKY 294 7-9 April 2008, pp. 1190-1191. A,rs: A com-001. ariables and Applications,” 3rd Edition, McGraw n In- E. Bach and J. Shallit, “Efficient Algorithm,” Algorithmic Number Theory, Vol. 1, MIT Press, Cambridge, M Hil1996.  R. Crandall and C. Pomerance, “Prime Numbeputational Perspective,” Springer, New York, 2 R. Schoof, “Elliptic Curves over Finite Fields and the Computation of Square Roots Mod p,” Mathematics of Computation, Vol. 44, No. 170, 1985, pp. 483-494.  R. V. Churchill, J. W. Brown and R. F. Verhey, “Com-plex Vl, New York, 1976.  B. Verkhovsky, “Cubic Root Extractors of Gaussiategers and Their Application in Fast Encryption for Time-Constrained Secure Communication,” International Journal of Communications, Network and System Sci-ences, Vol. 4, No. 4, 2011, pp. 197-204. doi:10.4236/ijcns.2011.44024  M. Rabin, “Digitized Signatures and Public-Key Func-tions as Intractable as Factorization,” MIT/LCS Technical Report, TR-212, 1979. Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY295 Appendix A1. Classification of Roots of 1,0 Modulo ,pq There are various types of unary roots: Definitions and notations:  11:1,0mod, ,Spq 112ss; (A.1) where  11:1,0mod(,)Ppq 1p (A.2) is the set of principal square roots of (1,0) of the first level. Then 21:mod,, kSs pqk1,2; (A.3) where 2112:mod,;kPpp pqk  1,2; (A.4) is the set of principal square roots of (1,0) of the second level. In general, 1,:modiikSs p,q; (A.5) where 1,:mod,iikPp pq (A.6) is the set of principal square roots of (1,0) of the i-th level. A2. Criterion of Quadratic Residuosity and General Algorithm Proposition 1.A: Let . 1mod 221kkNIf and only if 1121:, modkkNEcd GS, (A.7) then has a square root. In this case ,cd1:moRE dG; (A.8) and  1212mo,d,kkNxy RcGd. (A.9) A3. Quadratic Extractor Modulo ,1n Proposition 2.A: Let ,1Nn be a prime; mod41, but mod81.NN (A.10) If the norm of is co-prime with N, then square root ,cd,xy of  is equal ,cd 248,,modnxyRcdn where  21/4,mod,nRcdn1 . (A.12) Proof: First of all, if 21Nn is a prime integer, then n is even. Therefore (A.10) implies that 24n and 248n are integers. Then (A.11) and (A.12) imply that   2242,,,,modnxyR cdcdcdn,1.1(A.13) Since the cyclic identity (4) implies that  2,1,0mod,ncd n, then potentially  24n,mod,11,0;0,1;0,1.cdn  (A.14) Therefore,   222244441,0 if ,1,0;0,1 if ,1,0;0,1 if ,0,1;0,10,1 if ,0,1.nnnncdcdRcdcd (A.15) Since  0,11,122 mod,1n {see Subsec- tions 5.3}, then R does not exist if 2 does not exist [1,6]. Therefore ,cd is the Gaussian QNR . For more details see (32)-(34), (A.11), (A.12), Subsection 5.4 and eight examples in Table A1. Remark A1: Here 1, 9and10, 0 are quartic roots of 1, 0 modulo 10, 1. Indeed, od 10,1;310,,1mq0 0 od 10,1; 41,91mq0, (9) 32mod10,1;qq 4210,9.qq2,029210 1,0 21,1, 0 A4. Special Cyclic Identity Proposition 3.A: If :,Npq is prime, then  1,1,0mod,Nqp pq. (A.16) Remark A2: Although ,,pq qp, identity (A.16) holds because ,pq and ,qp are co-prime. Indeed, assumption that w q,, ,mod,up pqpq, where both u and w are integers, implies that and mod,.upqNwqpNpq  (A.17) However, (A.17) is impossible since the inverse of N odulo ,1; (A.11) m,pq does not exit. s Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY Copyright © 2011 SciRes. IJCNS 296 Table A1. {Quadratic root extraction where mod 41N and mod 81N}: ,n; 2:22mn5; :12zm+. ,cd (2,0) (3,2) (4,8) (6,7) (7,4) (9,2) (9,9) (10,1) 2/2,ncd (0, −1) (−1, 0) (1, 0) (−1, 0) (−1, 0) (0, 1) (0, 1) (−1, 0) ,zcd GQNR (9, 4) (6, 3) (6, 9) (5, 8) GQNR GQNR (9, 0) R na ±(10, 0) (1, 0) ±(1, 9) ±(10, 0) na na ±(1, 9) ,,zxy cdR na ±(6, 8) ±(6, 3) ±(1, 5) ±(2, 4) na na ±(10, 8) 2,xy *** (3, 2) (4, 8) (6, 7) (7, 4) *** *** (10, 1) i.e., 1; xynxy r . Example 1.A: , although  284,10mod5,21, 0Hence gcd4,10,5, 2291. 12; 12xnrynr . (A.22) Corollary 1A: If gcd,,,1, 0stpq , then Therefore, (A.20) and (A.22) imply   1,, 1,0mod,Nstqp pq (A.18)   111,,1,1 1,1,1,11,0 mod,.Q.E.D.rn rnnrnrrn nrnrnrnr12   Proposition 4.A: If n and r in modulus ,nr have different parities, then multiplicative inverse of exists and equals  , modulo ,rnn r(A.23)  11,1,1 2mod,.rnnr nrnrnr Example 2.A: Let n = 10, r = 3. Then .  113,1074,72,14,78,3 (A.19) Indeed, 3,108,31, 0mod10,3. Proof: First of all, ,nrCorollary 2A: If n and r in modulus  ,1,1mod,rnn rnr . (A.20) have dif-ferent parities and there exists multiplicative inverse of ,ab, then multiplicative inverse of ,,mod,ab nrrn also exists.Now let’s find integers x and y such that  1,1,1, 01,mod,xynrn r (A.21)