The Collatz Connection

There is one integer sequence, which is keeping me up at night sometimes if I start thinking about it. It is the sequence of odd integers, which do not have 5 as a Collatz exit point. Why don't they? What is so special about them? But most importantly, how can we predict the next term of this sequence? What is the formula? This sequence is not in OEIS. The first few terms that I found are:


Not found in OEIS
The Collatz Conjecture is important for integer factorization. I recently read a very nice explanation of why this problem is important. I came up with a couple of interesting sequences in this vicinity: A276260 and A276290 but the sequence described above is something that troubles me in a mathematical sense.

On a personal note, I just learned today that the mathematician who first thought of the Collatz problem died while attending a Mathematics Conference in the city I was born in.


Dreaming of Collatz Exit Points

A few years ago I talked about Collatz exit points. Some Collatz exit points are reached a lot more frequently than others.  In fact, it appears that most integers reach only one such point.

Here are the first few Collatz exit points: 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, 91625968981, 366503875925, 1466015503701, 5864062014805, 23456248059221, 93824992236885, 375299968947541

Note: I call them Collatz exit points because for each ai in the set above 3*ai + 1 = 2i+1

As I already mentioned here there are only 3 odd integers below 100, for which 5 is not a Collatz exit. Below 200 there are also only 3, below 300 there are also only 3.

It seems 5 is the most commonly occurring Collatz exit point for all odd integers below 1000.

What about below 10000?

What about below 100000?



Non-Complimentary Primes

On the other side of complimentary primes are the non-complimentary primes, which are primes p for which the order of 2 mod p is odd.

The first few primes are 2,7,23,31,47,71,73,79,89,103,127,151 and more can be generated here using the following Mathematica line
Select[Prime[Range[800]], OddQ[MultiplicativeOrder[2, #/(2^IntegerExponent[ #, 2])]]&]

In OEIS these primes are known as primes p that do not divide 2^x+1 for any x>=1.  What's interesting to me about these primes is that their exponentiation table follows a very different pattern than that of complimentary primes, and it all seems to be dictated by the order of 2 mod p.


Complimentary Primes

Definition: Complimentary primes are prime integers p such that 2k/2 mod p = p-1 where k is the order of 2 mod p.

Example: Let p = 43. It can be verified  that k = 14 since 214 mod 43 = 1 and 14 is the smallest such integer so 14 is the order of 2 mod 43. Since 27 mod 43 = 42 then 43 is a complimentary prime.

Verified result

The first few complimentary primes are 5,11,13,17,19,29,37,41,43,53,59,61,67,83,97,101.

This is a sequence documented in oeis.org (more or less) as the sequence of primes p where the order of 2 mod p is even. What isn't documented there and what I find special about complimentary primes is the following conjecture that I made:

Conjecture: If p is a complimentary prime and k is the order of 2 mod p then
(2i (mod p)) + (2(k/2)+i(mod p)) = p for all i greater or equal to 0

Example: Let p = 43. Since k is the order of 2 and k = 14, then k/2 = 7
20 mod 43 = 1  and  27 mod 43 = 42,
21 mod 43 = 2 and 28 mod 43 = 41,
22 mod 43 = 4 and 29 mod 43 = 39
23 mod 43 = 8 and 210 mod 43 = 35,
24 mod 43 = 16 and 211 mod 43 = 27
25 mod 43 = 32 and 212 mod 43 = 11,
26 mod 43 = 21 and 213 mod 43 = 22
27 mod 43 = 42 and 214 mod 43 = 1

You can use the iFrame below to find powers of 2 modulo an odd integer.


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


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


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)

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.


phi of n over 2 is just a number after all

Some people seem to have a hard time visualizing why my previous post is interesting. While proving the existence of a second private key does not break the RSA encryption algorithm, it does present a second attack vector especially for a certain subset of the set of products of safe primes.

Clearly, phi(n)/2 can be found if phi(n) is known. However, as I stated previously in this blog, for certain products of safe primes phi(n)/2 can be found without prior knowledge of phi(n).

In general, if n belongs to the set of these certain products of primes, then there exists an integer k mod n such that 2*k = n-1 and k^k = phi(n)/2 where phi(n) is Euler's Totient Function

One such product is the product of the 2 smallest safe primes, namely 5 and 7.


Given n = 35 then (n-1)/2 = 17 and 17^17 = 12, which is phi(35)/2


Proving The Existence Of A Second Private Key That Decrypts a Message Encrypted With The RSA Encryption Algorithm

While taking a course in cryptography 6 years ago I stumbled upon a problem that kept me awake at night for many nights.

In school we learn that the RSA encryption algorithm consists of one public key and one private key. I've asked several professors if there could be a second private key that decrypts all messages in the same way as the intended private key and I've always received a negative answer.

And yet I stumbled upon two private keys in one particular example. I delved into the Mathematics behind the RSA algorithm and I found out that in fact there are at least two keys in every single example. I not only managed to prove the existence of a second private key but I was also able to find two different formulas for obtaining the second key.

One of the formulas requires knowledge of phi(n)/2 where phi(n) is Euler's Totient Function.

If d1 is the intended private key and (n, e) is the public key then the second key d2 can be found using the following formula:

d2*e = phi(n)/2

Here's the full paper: https://marinaibrishimova.net/docs/otherkeys.pdf

Currently, I'm looking into ways of obtaining phi(n)/2 without having to factor n.


Products of Primes Without Selfie Powers

In my previous post I suggested that there are products of primes p and q that are easier (relatively) to factor because there is an integer k such that k = (p*q - 1)/2 and k^k = (phi(p*q))/2 and I called k a selfie power.

Before I talk about such products, I'll talk about products of primes, which have no selfie power and no semi selfie powers* because proper categorization is important.

Theorem: Given a product of primes p and q, if p or q divides phi(p*q) then p*q has no selfie power (ie an integer k such that k = (p*q - 1)/2 and k^k = (phi(p*q))/2 )

Proof: If p or q divides phi(p*q) then GCD(phi(p*q), k) = 1 since by definition of a selfie power k = (p*q - 1)/2 but also by definition of a selfie power k^k = (phi(p*q))/2 so 2*(k^k) = phi(p*q), which is a contradiction.

Example: Let p = 5 and q = 11, then p*q = 55 and phi(p*q) = (p-1)*(q-1) = 4*10 = 40 and clearly p divides phi(p*q). Furthermore, (p*q-1)/2 = 27 and 27^27 (mod 55) = 42 so 27 is not a selfie square as expected.

*to be defined in future blog posts