Int. J. Communications, Network and System Sciences, 2011, 4, 197-204
doi:10.4236/ijcns.2011.44024 Published Online April 2011 (http://www.SciRP.org/journal/ijcns)
Cubic Root Extractors of Gaussian Integers and Their
Application in Fast Encryption for Time-Constrained
Secure Communication
Boris Verkhovsky
Computer Science Department, New Jersey Institute of Technology, Newark, USA
Received March 2, 2011; revised April 12, 2011; accepted April 15, 2011
Abstract
There are settings where encryption must be performed by a sender under a time constraint. This paper de-
scribes an encryption/decryption algorithm based on modular arithmetic of complex integers called Gaus-
sians. It is shown how cubic extractors operate and how to find all cubic roots of the Gaussian. All valida-
tions (proofs) are provided in the Appendix. Detailed numeric illustrations explain how to use the method of
digital isotopes to avoid ambiguity in recovery of the original plaintext by the receiver.
Keywords: Cryptographic Protocol, Secure Communication, Time-Constrained Encryption, Cubic Root
Extractor, Gaussian Integers, Modular Arithmetic, Prefix/Suffix Positioning, Digital Isotope,
Quadratic Residue, Jacoby Symbol
1. Introduction
This paper describes a cryptographic algorithm based on
the extraction of cubic roots from complex numbers a + bi
with integer components a and b. Such complex integers
are called Gaussian integers (Gaussians, for short) [1].
Let’s denote and , where N
is called a norm of (a, b). In modular arithmetic based on
Gaussians, if p is a prime and , then for
every integer a and b holds an equivalent of the Fermat
identity [2]:

, :aba bi 2 :Nab
mod 0Np
2
1
 
21
,mod1,0
p
ab p
. (1)
This means that the cycles in Gaussian modular arith-
metic have order , while the cycles in modular
arithmetic based on real integers have order

2
p


p. Ap-
plication of Gaussians for ElGamal cryptosystem is con-
sidered in [3]; and the RSA digital signature is described
in [4]. Public key cryptography based on cubic roots of
real integers is provided in [5] and in [6].
Definition1: A Gaussian integer (x, y) is called the cu-
bic root of (a, b) modulo integer n, and defined as

3,modab n, if

3
,,mod
x
yabn. (2)
Proposition1: If p is a prime, and mod12 1p



13
:,mod 1,0
p
Vab p
1


, (3)
then there exists a cubic root of (a, b) modulo p.
Proposition2: If , then for every integer
a and b there exists an unique cubic root of (a, b) modulo
p.
mod12 5p
Proposition3: If and
2mod 91p

1
:mod1,0
p
WV p
1


, (4)
then there exists a cubic root of (a, b) modulo prime p.
Remark1: Here are examples, where 2mod 91p

: p
= 17, 19, 53, 71, 89, 107, 109, 179, 197, 199, 269, 271.
The following two algorithms are constructive proofs
of these propositions.
2. Algorithm-1
Step 1.1: Compute



213
:, mod
p
Wab p

; (5)
Step 2.1: if


1,0W, then cubic root of (a, b) mod-
ulo p does not exist;
Step 3.1: Compute
:mod9sp ;

(6)
{there are six possibilities};
= 1;2;4s

198 B. VERKHOVSKY
Step 4.1: if , then 1s
:4ms, (7)
otherwise apply Algorithm-2;
Step 5.1: Compute

2
:13
p
Emp


9


, (8)
{where m = 1 or 2, see Table 1};
Step 6.1: Compute

,: ,mod
p
E
x
yabp

4
. (9)
Example 1: Let p = 23; ;

,19,ab 
176
2
(23 1)/3
:(19, 4)(19, 4)mod 23(1,0);W  
:59
p
E
hence (19,4)
is a cubic residue. ;
  
59
3
,:19,419,4mod 2316,16.xy  


Indeed,
 
3
16,16mod 2319, 4. It is easy to verify that (5, 2)
and (2, 5) are also cubic roots of (19, 4). Hence, algo-
rithm (5)-(9) computes only one of three cubic roots of
(a, b). How to compute the two other cubic roots is dis-
cussed in sections 5 and A3.
3. Algorithm-2
If q mod 12 = 5, then a cubic root exists for every (a, b);
and each Gaussian has a unique cubic root. The follow-
ing algorithm computes such a cubic root (1).
Step 1.2: Compute cubic extractor

:2 13
q
Eq ;
Step 2.2: Compute (10)

:, mod
q
E
Rab q
Step 3.2: Output (x, y):=R.
Three examples are provided in Table 2.
4. Multiplicity of Cubic Roots
Proposition 4: Suppose are three cubic
12
, and CC C
3
Table 1.Cubic extractors
p
E
and m.
p 7 11 13 23
p
E; m 5; 2 27; 2 19; 1 59; 1
p 29 31 41 43
p
E; m 187; 2 107; 1 187; 1 411; 2
Table 2. Illustrations of cubic root extraction; q mod 12 = 5.
q; (a, b) 53; (19, 13) 89; (17, 77) 269; (19, 73)
q
E 35 59 179
(x, y) (45, 28) (6, 85) (112, 124)
roots of L:= (a, b) modulo p, each satisfying the equation


3mod 0CL p

; (11)
then for every i = 1, 2, 3 the following identities hold:
3mod
i
CL p. (12)


123
123
mod0;
mod [7];
CCC p
CC CpL
 



12 1323mod 0.CCCC CCp


(13)


2mod 0
ij k
CC Cp

, (14)
where {i, j, k} is every permutation of {1, 2, 3}.


2mod 0.
ij ij
CC CCp






 (15)
5. Cubic Roots of (1, 0) and Gaussians
In order to find two other roots of (a, b), consider cubic
roots of unity:

3
,: 1,0moduw n. (16)
If (x, y) is a cubic root of (a, b), then



,,uwxy and

2
,,moduw xyp are also its cubic roots modulo n.
Proposition 5: If p is a Blum prime, then either
3or3

modulo p exists, but not both; if 3 mod p
exists, then



12mod;
and 132mod.
up p
wp





p
(17)
If 3modp exists, then


13modu p
. (18)
Proof is provided in the Appendix.
6. Existence of 3 modor3modpp
Jacoby symbols [8,9] analyze whether a specified integer
is quadratic residue (QR). If p is a Blum prime, then


2
31/8
3mod31
1
33
2
or 11.
3
p
p

 

 

 


 



 





(19)
Therefore, if p mod 12 = 11, then 3 is QR. Seven ex-
amples are listed in Table 3.
Table 3. 3mod
p
if p mod 12 = 11.
p 11 23 47 59 71 83 107
3 5 16 12 48 43 70 89

B. VERKHOVSKY
199


,;
mod;
p
Yet, if p mod 12 = 7, then –3 is QR. (20)
7. Properties of Gaussian Cubes
Consider
 


322 22
,:,3, 3modtvuwu uwwuwp (21)
Property 1:




322 22
,3,3uwuuwwu wtv
(22)
Property 2:

 
322 22
,3,3(,)wuw wuuwuvtp
(23)
Property 3: If u + w = p, then
 
33
3
,, mo1d1,uuwwu . (24)
8. Cryptographic Protocol
System design (each user’s actions):
Step 1.3: Selects two large distinct primes p and q,
where p mod 12 = 11; ; and q mod 12 = 5;
2mod 91p
Step 2.3: Computes n = pq; {n is user’s public key; p
and q are his private keys};
Step 3.3: Finds cubic root (u, w) of (1, 0) modulo p:


12mod;3mod.uppwu p
Step 4.3: Pre-computes




11
:mod; :modmod;PqqpQ ppqn


Protocol implementation: Suppose a sender (Sam)
wants to securely transmit a plaintext G to receiver (Re-
gina);
Sam divides G into an array of blocks
  


112 2
,; ,;; , ;
kk
ghghgh
and
kk
 in such a way that
every
g
nhn;
Encryption {Sam’s actions}:
Step 5.3: He gets Regina’s public key n; computes
ciphertext

3
,:, modab ghn;
and sends (a, b) to her;
Decryption {Regina’s actions}:
Step 6.3: She, using her private keys p and q, extracts
cubic roots
 
33
1:,mod; and :,mod;
M
abpR abq
Step 7.3: She computes
 
21 32
:,mod ; and :,mod ;
M
Muw pMMuw p
Step 8.3: {Using Chinese Remainder Theorem [10], Re-
gina computes all 3 roots of (a, b)

3
:,modDabn }:
for k = 1,2,3


:m
kk
DMPRQodn;
Step 9.3: {The original plaintext is recovered via dig-
ital isotopes-see sections 10 and 11}: D = G.
9. Efficient Encryption of Gaussians
Squaring of a Gaussian requires two multiplications of
real integers (MoRI); and multiplication of two Gaus-
sians requires three MoRI [11]. Therefore, the cubic
power of Gaussian requires five MoRI. Yet, encryption



33223
,:,3 ,3modabghgghgh hp
in Step 5.3 requires only four MoRI:
22
12
12 32 41
33 44
:mod;:mod;
:;:2;:2
:mod;:mod;
PgpPh p
SPP AS P A S P
PgA pPhAp

 

;
{there are no 1
A
and 2
A
}; where the doublings
are achieved by binary shifting; then
1
2 and P
2
2P




34
,P P,:ab.
10. Asymmetric Tagging of Digital Isotopes
In cryptographic algorithms based on extraction of square
roots of real integers [12] or Gaussians [6] there are four
pairs of solutions, and only one of them is the original
plaintext. To distinguish the original solution from the
other three, the authors use methods of tails, which is an
analogue of using isotopes to tag various chemical com-
ponents.
If the digital isotopes repeat r rightmost digits in each
component of plaintext (g, h), then the probability of
erroneous recovery of the “plaintext” is of order


2
110r . For instance, if the length of isotope r = 3,
then the probability of error is one in one million.
As shown below, a more elaborate strategy must be
used to avoid ambiguity in the recovery of the original
plaintext.
Definition 2: If there exist Gaussians with distinct
components x and y such that

33
,,mod

x
yyx p, (25)
then such cubic roots are called Gaussian twins (or CT,
for short).
Proposition 6: If the square root of 3 modulo prime p
exists, then there exists the CT; {see Table4 for examples}.
Table 4. Examples of cubic roots twins (CT) for p = 83.
(a, b) (27, 56) (31, 52)(26, 57) (2, 81) (78, 5)(53, 30)

3,ab (22, 76);
(76, 22)
(15, 24);
(24, 15)
(46, 8);
(8, 46)
(77, 7);
(7, 77)
(8, 5);
(5, 8)
(1, 11);
(11, 1)

B. VERKHOVSKY
200

0
Proof: since , then (25) implies the
following relationships:

mod 0xy p
 



 
22
2222 22
2
2
1, 1,,,,0;
,2 0,,2
0, 2mod0;
.., 2mod0.
x yxyxy yxyx
xy xyxyy x xy
xyxyp
iex yxyp

 


 

 

(26)
Let y := Txmod p, then 
i.e., which implies that

2
212modxTTp

 ,
0;

241modTT p
23modTp .
For instance, if p = 83, then 370, i.e.,
.

270mod8311 or 68T
If x = 1, then y = {11 or 68}; hence
; and
.
 
33
1,6868,1 mod8373,10

33
1,1111,1mod 8353,30

It means that

353,30mod83 equals either


1,11
or . Yet, if in both components the rightmost digit
is “1”, it is not clear whether the original plaintext is (0,
1) or (1, 0). For every p mod 12 = 11 there exist
CTs that satisfy (25) {examples are provided
in Table 4).

11,1

41p



11. Numeric Illustration
Algorithm in a nutshell
System design: Let Regina’s p = 227 and q = 1109,
where , p mod 12 = 11; and q mod 12 = 5;
she computes n = pq = 251,743; P and Q:
2mod 941p


11
11
:mod=11091109mod 227
1109 96106464;
:=mod227227mod1109
227 640145280;
Pqq p
Qpp q






and a cubic root (u w) of (1,0) modulo p:

22712 mod113up ;
57
31133mod 22725;wu 
Remark 2: ;

2
,,moduwup wp
 
3
, 25mod 2271, 0


{indeed, ;
113
 
2
and
113,25mod 227113,202};
:227 mod 9 2s; :42 2m;
and Gaussian cubic extractor {Step 5. 1}


2
: 2 2271 3911451
p
E 

;
finally, Regina pre-computes another cubic extractor


:2 13739
q
Eq .
Encryption: Suppose the sender (Sam) wants to se-
curely transmit message G = (1941, 2487) to Regina with
two-digit isotopes:
Z := 100G + Gmod100 = (194141, 248787).
In this case the probability of erroneous recovery of
the original message will not exceed 1/10,000, i.e., it
equals 0.01%.
Sam computes ciphertext


3
,:mod 251743227258,195067ab Z


Decryption: Regina computes

 
11451
1
11451
:227258,195067mod 227
31,74mod22774,78
M

and two other cubic roots:



 
21
:,74,78113,2556, 222;MMuw








32
:,56,222113,2597,154;MMuw
and then unique cubic root R modulo q
 
 
739
: ,mod227258,195067
66,371mod1109.
q
E
Rab q

Using the Chinese Remainder Theorem [10], Regina
computes (28):
System design: Select p, q;
Compute n, P, Q, u, w, s, m, ,
p
q
Encryption: Create plaintext Z with isotopes; com-
pute ciphertext (a, b);
EE;
Decryption: R; RQ; 12 ;;





1
1
,11091109mod 227
227227mod1109mod251743
106464145280mod251743;
k
k
k
xy M
R
MR






 

3
M
MM.
until she detects isotopes


 

1
1
,106464145280 66,371
10646474,7822246, 25878mod
96549,274294;where251743
xy M
n
n









 

2
2
,10646422246,25878mod
10646456,22222246, 25878mod
1941, 2487.
xy Mn
n


 

41 87
Therefore, Regina recovers the original Gaussian
block of information; and it is not necessary to compute


3
,
x
y.
12. Optimized Recovery of Information
Let

 
12 12
, ; ,
kkk
M
MM RRR;

B. VERKHOVSKY
201
then 112 2 ;
kk kk
x
MP RQyMP RQ .

11112
, MMM

is computed by cubic root extraction;
if the isotopes in Z are detected, then the original infor-
mation is recovered; otherwise Regina needs to compute
four components of two other cubic roots of (a, b):


21112
1112 1112
, (,)
,
MMMuw
M
uMwMwMu

 ; (27)


31112
11 121112
, ,
,
MMMuw

M
uMwMwMu

. (28)
Yet, to minimize computational burden, instead of
computing 2 and 3
M
M, she finds
112
:NMwP; (29)
and then computes


211111
x
MuP RQN. (30)
If the isotopes are detected, then she computes ,
otherwise Regina computes
2
y
 
32 1
11 11123
2
and .
xx N
M
uPRQMwPy

 (31)
13. Elimination of Ambiguity in Recovery of
Original Information
The probability of erroneous recovery can be decreased
if, instead of repeating r rightmost digits of g and h, the
following procedure is applied:
1) Consider r leftmost digits (prefix r P) of the first
component g in plaintext (g, h) and repeat it as its
digital isotope;
2) Consider r rightmost digits (suffix r S) of the sec-
ond component h of plaintext (g, h) and repeat it as
its digital isotope.
Example 2: if (g, h) = (31415926, 27182845) and r = 2,
then (3131415926, 2718284545).
NB: if n is t-digits long and the number of digits in g
is smaller than t, then the prefix . To avoid
ambiguity, the sender must attach both digital isotopes
r and r as suffixes. Below is a simple mne-
monic/schematic rule for constructing the digital isotopes:
00 0
r
P
P S


priority, cocktail
rity, cock.prio tail

prio tail

Remark 3: Therefore, there can be two types of cubic
roots with isotopes:
(PUP, VSS) and (USS, PVP). Only the former one is
authentic. Hence, a receiver (Regina) searches for the
cubic root with isotopes in format (PUP, VSS), where P
and S are prefix and suffix respectively. In this case (PU,
VS) is acceptable as the genuine plaintext.
Example 3: if t = 8; r = 2;
and (g, h) = (00415926, 07182845),
then

68
22 2
(mod10 )10,
:
(mod10 )10mod10 )
00415926,07182845
gg g
Z
hh h






00 45
14. Second Numeric Illustration
System design: Let p = 227; q = 1109, n = pq = 251,743;
P = 106464; Q = 145280; (u, w) = (113,25); 2s

;
2m

; 11451;
p
E

739
q
E

.
Encryption: Plaintext G = (1756, 2011); plaintext with
isotopes
Z := (175617, 201111);
and ciphertext (a,b) = (57971, 209989);
Decryption: R = (395, 382); M := (202, 137);
1mod239939;QRn 
112
: 115336NMwP


196xM uPQRN
;
21111688

 ;
since there is no isotope in 2
x
, then

33
,
x
y is the
original Gaussian.
Indeed, 321 21756xx N

17 .
15. Algorithm Analysis
The cryptographic algorithm described above is neither a
generalization nor a special case of the RSA protocol
[13].
First of all, the following identity holds:





211
,mod1,0
pq
ab n
 1. (32)
In the RSA algorithm, if z is the length of group cycle
[13], then each user selects a public key e that is
co-prime with z. In the proposed algorithm the length of
cycle c is equal



2
:1cp q

1


. (33)
Therefore in the RSA extension it would have been
necessary to compute a multiplicative inverse d of e
modulo c. Yet, in the algorithm described above the en-
cryption key e = 3. Hence, the decryption key d cannot
be computed as a modular multiplicative inverse, since


gcd 3,3z

, which implies that such an inverse does
not exist [14].
16. Communication Speed-Up
Suppose it is necessary to transmit an H digit-long plain-

B. VERKHOVSKY
202
text, where the size of each block must not exceed six-
teen digits; in addition, suppose that we want to ensure
that the probability of erroneous recovery does not ex-
ceed one in one million. There are two options:
Option 1 is to select the size of each block equal to ten
digits and the size of each tail equal to six digits; Option
2 is to select the size of each block equal to thirteen dig-
its and the size of each tail equal to three digits.
In the 1st option we will treat each block individually
as a real integer; which implies that we need to transmit
H/10 real integers. In the 2nd option we will treat a pair of
blocks as a Gaussian; which implies that we need to
transmit H/26 Gaussians, i.e., H/13 real integers. There-
fore, the first option requires 13/10 = 1.3 times more
bandwidth, than the second option. In other words, the
bandwidth can be reduced by 30% if Gaussian integers
are considered.
17. Possible Applications and Conclusions
The proposed cryptosystem has significant specifics: the
encryption is substantially faster than the decryption.
There are certain settings where the sender has limited
time to transmit the message: visual images or video, and
receiver does not have such restriction. For instance, the
sender is a system that urgently needs to transmit infor-
mation prior to either collision with a target or before it
is destroyed by a hostile action [15]. Another example is
if the sender (say, an interplanetary or interstellar space
station) detects an impending collision with an asteroid
and is programmed to report about such collision and
transmit visual and other details about the asteroid.
In this case it is paramount to ensure the reliability of
message delivery [15,16]. Yet another example is of a
security camera that has detected an imminent explosion
and is pre-designed to report the situation (audio, pic-
tures and/or video) [17] prior to its own destruction from
the explosion.
18. Acknowledgements
I express my appreciation to J. Jones, and R. Rubino for
corrections, and to E. A. Verkhovsky as well as anony-
mous reviewers for several suggestions that improved
this paper.
19. References
[1] C. F. Gauss, “Disquisitiones Arithmeticae,” English
translation, Yale University Press, New Haven, 1986.
[2] J. T. Cross, “The Euler’s φ-Function in the Gaussian In-
tegers,” American Mathematics, Vol. 55, 1983, pp.
518-528. doi:10.2307/2322785
[3] A. N. El-Kassar, M. Rizk, N. Mirza and Y. Wada, “El-
Gamal Public Key Cryptosystem in the Domain of Gaus-
sian Integers,” International Journal of Applied Mathe-
matics, Vol. 7, No. 4, 2001, pp. 405-412.
[4] H. Elkamchouchi, K. Elshenawy and H. Shaban, “Ex-
tended RSA Cryptosystem and Digital Signature Schemes
in the Domain of Gaussian Integers,” The 8th Interna-
tional Conference on Communication Systems, Washing-
ton, 25-28 November 2002, pp. 91-95.
[5] S. Kak, “The Cubic Public-Key Transformation,” Cir-
cuits Systems Signal Processing, Vol. 26, No. 3, 2007, pp.
353-359. doi:10.1007/s00034-006-0309-x
[6] B. Verkhovsky, “Accelerated Cybersecure Communica-
tion Based on Reduced Encryption/Decryption and In-
formation Assurance Protocols,” Journal of Telecommu-
nication Managements, Vol. 2, No. 3, 2009, pp. 284-293.
[7] R. W. Hadden, “On the Shoulders of Merchants: Exchange
and the Mathematical Conception of Nature in Early
Modern Europe,” State University of New York Press,
New York, 1994.
[8] R. Crandall and C. Pomerance, “Prime Numbers: A
Computational Perspective,” Springer, New York, 2001.
[9] A. Menezes, P. van Oorschot and S. Vanstone, “Hand-
book of Applied Cryptography,” CRC Press, Boca Raton,
1997.
[10] D. Knuth, “The Art of Computer Programming, Vol. 1:
Fundamental Algorithms,” 3rd Edition, Addison-Wesley,
Upper Saddle River, 1998.
[11] A. Karatsuba and Y. Ofman, “Multiplication of Many-
Digital Numbers by Automatic Computers,” Doklady Ak-
ademii Nauk SSSR, Vol. 14, No. 145, 1962, pp. 293-294.
[12] M. Rabin, “Digitized Signatures and Public-Key Func-
tions as Intractable as Factorization,” Technical Report,
MIT/LCS/TR-212, January 1979.
[13] R. Rivest, A. Shamir and L. Adleman, “A Method of Ob-
taining Digital Signature and Public-Key Cryptosys-
tems,” Communication of ACM, Vol. 21, No. 2, 1978, pp.
120-126. doi:10.1145/359340.359342
[14] B. Verkhovsky, “Enhanced Euclid Algorithm for Modu-
lar Multiplicative Inverse and Its Complexity,” Advances
in Computer Cybernetics, Vol. 6, 1999, pp. 51-57.
[15] B. Verkhovsky, “Selection of Entanglements in Informa-
tion Assurance Protocols and Optimal Retrieval of
Original Blocks,” Journal of Telecommunications Man-
agement, Vol. 2, No. 2, 2009, pp. 186-194.
[16] B. Verkhovsky, “Information Assurance Protocols: Effi-
ciency Analysis and Implementation for Secure Commu-
nication,” Journal of Information Assurance and Security,
Vol. 5, No. 3, 2008, pp. 263-269.
[17] Z. Xu and J. Sun, “Video Encryption Technology and
Application,” English translation, Nova Science Publishers
Inc., New York, 2010, pp. 1-99.

B. VERKHOVSKY
203
Appendix
A1. Validation of Algorithm-1
If condition (5) holds; then
 




2
2
131
13
33
,,
m
,
,od,
pmp
m
p
E
xy ab
p
ab
ab ab







(A1)
If



213
,mod1
p
ab p


,0, then by Definition (2)
(x, y) is a cubic root of (a, b) modulo prime p. Hence, if

219p is not an integer, then there exists an integer
m such that
p
E is an integer, i.e., there exists an integer
solution of equation

213mod90mp

 

. (A2)
Indeed, observe that
1) Every integer greater than 3 can be expressed ei-
ther as p=6k+1 or as p = 6k–1;
2)

213p is an integer for every prime greater
than 3;
3) If

219p is not an integer, then k mod 3 = 0;
and

213p is not co-prime with 3.
Therefore, (A2) can be rewritten as

213mod3 2mp
. (A3)
If there is no integer solution of Equation (A3); then
Algorithm-1 is not applicable for these cases. In other
terms, if either

19p or

19p is an integer,
then
p
E is not an integer.
A2. Validation of Algorithm-2
Let



2
1
3,,m
q
Rabab



 odq
. (A4)
Since q mod 12 = 5, then


12q is even, hence by
Euler criterion of quadratic residuosity
, i.e.,


1/2
1mod
qq 
1


:1modip q (A5)
is a real integer; and hence (a, b)mod q is also a real in-
teger. Therefore, by the Fermat identity
. Q. E. D.

3mod ,Rqa

b

A3. More on Identities for Cubic Roots
By the Vieta theorem [7], equation

3mod 0CL p; (A6)
implies that
 
123
mod 0CC CCCCp  . (A7)
Hence, (A6) and (A7) imply


123 123
mod0; mod;CCCpCCCpL

  (A8)
and for every permutation {i, j, k} of


1, 2, 3


2mod 0
ij k
CC Cp. (A9)
On the other hand, (A9) implies

2mod 0.
ij ij
CC CCp





 (A10)
Yet, neither (A9) nor (A10) are instrumental in recov-
ery of all cubic roots.
A4. Proof of Proposition 5
Algebraic approach:




33223
,3,3moduwuuwuw wp1,0 (A11)
Therefore from (A6) we deduce two equations with
unknown u and w:


22
3moduuwp1

; (A12)
and


22
3modwu wp0

. (A13)
Since in (A13) mod 0wp

, then

22
3moduw p

. (A14)
Hence, (A12) and (A14) imply that




3
2
810mod; or
214 21mod 0
up
uuu p

.

 
(A15)
Equation (A15) holds if either

 
12modup p ; (A16)
or


2
421moduu p0

. (A17)
Thus in (A16) case, if there exists square root of 3
modulo p, then from (A14)


31wu p 32. (A18)
Otherwise, Equation (A17) implies that
13modu p; (A19)
and finally from (A12) we deduce w.
Trigonometric approach: Consider



33
,1,0cosπisinπ
(cos π3isinπ3)1,32 mod
uw
p
 
  (A20)

B. VERKHOVSKY
204
.
Proposition7: If (x, y) is a cubic root of
(a, b) modulo p, then and

,,moduwxyp

2
,,moduw xyp are also cubic roots of (a, b).
Proof: From Definition1 (2) for k = 1, 2

3
,, ,mod
k
uw xyabp


 Q.E.D.