The new cryptological system and other results - Cryptoslovak.sk

The new cryptological system and other results related to the discovery of number theory

Ivo považan
pensioner
Slovakia
Bratislava
e-mail: i.povazan@upcmail.sk
mobil: +421 944 662 674
Version 0.9


28. mája 2017

Function _x (n)

We define the following functions _x(n):

$$For\;a\;prime\;p = 4k + 1,x(p) = p - 1,$$

$$For\;a\;prime\;q = 4k - 1,x(q) = q + 1,$$

$$x(p^\alpha) = p^{\alpha - 1} (p - 1)$$

$$x(q^\alpha) = q^{\alpha - 1} (q + 1)$$

$$x(2^\alpha) = 2^{\alpha - 1}$$

$$If\;gcd(m,n) = 1,\;then\;x(mn) = x(m)x(n).$$

Function _x(n) is similar to Euler's totient function.

Binary Quadratic forms

Binary Quadratic Forms:

$$\boldsymbol q = ax^2 + bxy + cy^2$$

Discriminants of Forms:

$$\Delta = b^2 - 4ac.$$

Next we will only work with forms:

$$\Delta = -(2dN)^2\;N\;is\;odd\;a\;d = 2^0,2^1,2^2,...$$

Principal Forms:

$$(1,0,-\frac \Delta 4) - we\;will\;label\;it\;\boldsymbol 1$$

A form (a, b, c) is said to be primitive if:

$$gcd(a,b,c) = 1$$

A form (a, b, c) is said to be ambiguous if:

$$(a,\;b,\;c)\;is\;equivalent\;to\;(a,\;-\;b,\;c)$$

The class number h(Δ) is the number of proper equivalence classes of primitive integral forms of discriminant Δ.
Class number:

$$\boldsymbol cl = x \left(\frac {dN}2\right)$$

$$and$$

$$\boldsymbol q^\boldsymbol{cl} = \boldsymbol 1$$

A special case:
If N is a prime of type p = 4k + 1 and d = 2,

$$\boldsymbol q^{p-1} = 1$$

If N is a prime of type p = 4k - 1 and d = 2,

$$\boldsymbol q^{p+1} = 1$$

The sketch of the proof is in the examples 1 and 2, which are in the next section.

Composition of Forms

$$m = gcd \left( a_2,a_1, \frac {b_1+b_2}2 \right)$$

and

$$a = \frac {a_1 a_2}{m^2}$$

Moreover, let j, k, l ∈ Z such that

$$m = ja_2 + ka_1 + l \frac {b_2+b_1}2$$

$$b \equiv \frac {ja_2b_1 + ka_1b_2 + l \frac {b_1 b_2 + \Delta}{2}}{m}\;\;mod\;2a$$

$$c = \frac {b^2 - \Delta}{4a}$$

Canonic Form

$$\Delta = b^2 - 4ac$$

$$\Delta = - \left( 2\cdot d\cdot N \right)^2$$

$$4ac = b^2 - \Delta$$

$$if\;b = 2kN\;than$$

$$4ac = 4k^2N^2 + 4\cdot d^2 \cdot N^2$$

$$a = N^2$$

$$c = k^2 + d^2$$

In most cases, the composition of two forms can be reduced to the calculation of k₃.

$$Qfb(N^2,2k_1N,d^2+k_1^2) \cdot Qfb(N^2,2k_2N,d^2+k_2^2) = $$

$$Qfb(N^2,2k_3N,d^2+k_3^2)$$

$$k_3 = \frac {k_1k_2 - d^2}{k_1 + k_2}\;mod\;N$$

The following equations are given for interest.

$$K_3 = (k_1 + d \boldsymbol i) (k_2 + d \boldsymbol i)$$

$$\Re (K_3) = k_1\;k_2 - d^2$$

$$\Im (K_3) = d\;k_2 + d\;k_1$$

Example 1: d = 2;N = 127;N%4 = 3 N is prime.

Example 2: d = 2;N = 101;N%4 = 1 N is prime.

$$Reduced\;binary\;quadratic\;form\;is\;repeated\;with\;period\;N.$$

$$The\;principal\;form\;is\;not\;there\;and\;therefore\;needs\;to\;be\;added.$$

$$We\;have\;N + 1\;forms.\;It\;only\;applies\;if N \equiv 3\;mod\;4.$$

$$If\;N\; \equiv 1\;mod\;4\;then\;in\;each\;period\;there\;are\;two\;forms\;that\;are$$

$$not\;primitive.\;We\;have\;N - 1\;forms.$$

$$N\;can\;be\;expressed\;as\;N = a^2 + b^2.$$

Cryptologic system

$$N = pq$$

$$ed \equiv 1\;mod\;x(N)$$

$$ed = 1 + k\;x(N)$$

$$\boldsymbol q^{ed} = \boldsymbol q^1 \boldsymbol q^{(kx(N))}$$

$$(\boldsymbol q^e)^d = \boldsymbol q$$

Primality test

Conjecture:

Let N = 4k - 1 be a natural number . N is prime if and only if:

$$2^{N-1} \equiv 1\;mod\;N$$

$$and$$

$$\boldsymbol q^{N+1} = \boldsymbol 1$$

Programs for Test

All test programs are written in PARI / GP language. Usage is in source code comments.
1.file phb.gp download - public-key cryptosystems.
2.file pr.gp download - primality test.
3.file poll.gp download - integer factorization.
4.file mer.gp download - primality test for Mersenne numbers.
5.file fchi.gp download - Compare _x() and classnumber() functions.

PDF file download