17.10.18

Self-sufficient exponents

Definition: A self sufficient exponent e is an exponent such that (me (mod n))e (mod n) = m for all m < n.

Conjecture: If n is a positive integer greater than 6, then there are at least 2 self-sufficient exponents smaller than lcm((p-1)(q-1)).

Example: Let n = 35, then 5, 7, 11 are self sufficient exponents because for all m < 35 (m^5)^5 = m, (m^7)^7 = m, (m^11)^11 = m. But also 17, 23, 29 are self-sufficient exponents.

Let n = 77, then 11, 19, 29 are self-sufficient exponents because for all m < 77 (m^11)^11 = m, (m^19)^19 = m, (m^29)^29 = m. But also 41, 49, 59 are also self-sufficient exponents.

Conjecture: If n is the product of two distinct odd primes p and q and k = ((lcm((p-1)(q-1))) - 1) then k is a self-sufficient exponent.

This has to do with the structure of the exponentiation table of Z sub n when n is the product of two distinct odd primes. https://en.wikipedia.org/wiki/RSA_(cryptosystem), last retrieved 17/10/18

26.9.18

Finding a primitive root

I was just going over some old posts when I realized that I haven't talked about how to check if an integer k is primitive root of a prime p or a power of a prime p^r.

Conjecture: If k^((p-1)/2) mod p is equal to (p-1) then k is a primitive root of p.

To check if k is a primitive root of p:

1. Compute x = k^((p-1)/2) mod p
2. If x == (p-1) then k is a primitive root of p

For example, Let p = 11.
2 is a primitive root of 11 and 2^5 = 10 mod 11

Conjecture: If k^(((p-1)(p^(r-1)))/2) mod (p^r) is equal to (p^r - 1) and k is the smallest such integer then k is a primitive root of p^r.

Note that there might be other primitive roots other than the smallest one.

As discussed many many many times on this blog only p, p^r, 2p, or 2p^r where p is some prime and r is an integer greater than 0 have primitive roots. All other integers do not.

1.5.18

Fun With Steganography

Steganography is the art of hiding secrets in plain sight. Modern algorithms allow the concealment of vast amounts of data into a single digital image without making significant changes to the image typically by appending the data into the least significant bits of the red, blue, or green channels of a pixel in an image.

This method of hiding binary strings into colour channels does not work for jpeg images because jpeg is a lossy format and it compresses the RGB information upon saving but it does work for lossless formats like png and bmp. For example, using 2 least significant bits we can hide 1.5 MB of data in a
desktop background image but if we only want to hide a 128 bit integer we can do so in the alpha channel of particular pixels.

A 128 bit integer is at most 39 digits long. Each digit is an integer between 0 and
9, which can be hidden in the alpha channel of consecutive pixels of a PNG
image. The alpha channel is the transparency channel and it is usually set to 0 unless the image contains transparent pixels. For example, in PHP's GD library the alpha channel of a pixel in a png image is an integer between 0 and 127 where 127 means that the pixel is transparent. Therefore changes to this channel such as increasing it to an integer less than 9 do not affect the overall appearance of the image. Furthermore, if the alpha channel of every other pixel in that image is made to be an integer between 0 and 9 then it would be hard to identify which pixels contain the message unless the starting point of the message is known.

Thus the starting point of the message is the key to retrieve the message from the image. One of the images below has a secret message in it and the other one has no transparency channel.

Below is the pseudocode for the ensteging and desteging functions respectively. I implemented this algorithm using PHP's GD library and the code and a demo are available here.

ENSTEG Function
1. For each pixel at location x == key*
a. Add a digit from msg array to alpha channel, move onto next digit
b. Save pixel
2. Add random digits to the alpha channels of other pixel as distraction

*where key = timestamp of image upload mod width/2 for example

DESTEG Function
1. For each pixel at location x == key
a. Grab alpha value
b. Put value into array
c. Return array

4.1.18

Prime factorization using the smallest square root of a particular integer

If n is the product of two distinct odd primes p and q, then there are 4 square roots for each squared integer a such that GCD(a,n) = 1. There appears to be a relationship between the smallest square root of ((n+1)/2)^2 (mod n) and a multiple of p or q.

Conjecture 1.: Let n be the product of two distinct odd primes p and q. If s is the smallest square root of ((n+1)/2)^2 (mod n) then (n+1)/2 - s = rp such that GCD(rp, n) = p

Empirical evidence suggests that this conjecture holds for any n as long as n is the product of two distinct primes. In fact, the following algorithm can be used to factor n.

1. Calculate k = ((n+1)/2)^2 (mod n)

2. Find the smallest square root s of k mod n

3. Calculate xp = (n+1)/2 - s

4. Return GCD(xp, n)

Example:
a. Let n  = 35

1. k = 18^2 (mod 35) = 9
2. s = sqrt(9) = 3
3. xp = 18 - 3 = 15
4. GCD (15, 35) = 5

Step #2 can be further divided into two cases. The first case relates to k being a perfect square. If k is a perfect square then there is no need to use modular arithmetic to calculate the smallest square root of k. All known algorithms for computing the square root of a perfect square in Z will return the smallest square root of k. However, if k is not a perfect square in Z then finding its square root in Z_n becomes a different problem altogether.