A342754 Irregular triangle read by rows: T(n, k) is the number i of iterations that every scytale of length n and k > 1 sides must process its own ciphertext before the initial plaintext returns, where k | n, k > 1 and (n-1) | (k^i-1).

2, 4, 4, 3, 3, 2, 6, 6, 10, 5, 5, 10, 12, 12, 6, 6, 4, 2, 4, 8, 16, 16, 8, 18, 9, 9, 18, 4, 4, 6, 6, 11, 11, 11, 11, 11, 11, 2, 20, 20, 3, 3, 18, 9, 9, 18, 28, 28, 14, 14, 28, 28, 5, 5, 5, 5, 8, 8, 10, 10, 16, 16, 12, 12, 6, 2, 6, 12, 12, 36, 36, 18, 18, 12, 6, 4, 4, 6, 12

Offset: 1

Author

Rodrigo Panchiniak Fernandes, Mar 20 2021

Keywords

• nonn
• tabf
• easy

Comments

Each number in this sequence is the number of times a scytale has to be fed with its own ciphertext until the apparatus generates back the initial plaintext because for every n/m integer, n > m > 1 and every integer i > 1, n^x mod (m-1) != n^i+1 mod (m-1). Tertium non datur: if n^i mod (m-1) = n^i+1 mod (m-1), i = i + 1, an absurdity. And this is why a recursive scytale does not freeze. Moreover, according to modular arithmetic, if n mod m = 1, then n +- (i*m) mod m = 1. This is why after a certain number of iterations the scytale returns the initial plaintext. Finally, for every integer y > 1, if n^i mod (m-1) = 1, then n^(y*i) mod (m-1) = 1, i < y*i. And this is why there is a first number of iterations for returning the initial plaintext, QED.

Examples

			Irregular triangle begins:
  00|01|02|03|04|05|06|...
  01|  |  |  |  |  |  |
  02|  |  |  |  |  |  |
  03|  |  |  |  |  |  |
  04|  | 2|  |  |  |  |
  05|  |  |  |  |  |  |
  06|  | 4| 4|  |  |  |
  07|  |  |  |  |  |  |
  08|  | 3|  | 3|  |  |
  09|  |  | 2|  |  |  |
  10|  | 6|  |  | 6|  |
  11|  |  |  |  |  |  |
  12|  |10| 5| 5|  |10|
  13|  |  |  |  |  |  |
  ...
		

References

• Rodrigo Panchiniak Fernandes, OpenPGPjs in Drupal: Practical Privacy-Driven Web Development, Apress (Springer), 2021, 35-40. (in press)

Links

• Rodrigo Panchiniak Fernandes, Table of n, a(n) for n = 1..10000
• Rodrigo Panchiniak Fernandes, Initial question, Cryptography Stack Exchange.
• Wikipedia, Scytale

Crossrefs

Row n is contained in row n-1 of A216327.

Cf. A139366.

Programs

JavaScript

// m = 1..10000
let n = 0n;
let a = [];
for (let m = 1n; m < 10001n; m = m + 1n){
  for (let k = 2n; k <= m; k = k + 1n){
    if ((m % k) == 0n){
      let xmod = 1n;
      for (let x = 1n; xmod != 0n; x = x + 1n){
        xmod = ((k ** x) - 1n) % (m - 1n);
        if (xmod == 0n && x != 1n){
          a[n] = x;
          n++;
        }
      }
    }
  }
}
console.info(a.join(','));

Maple

with(numtheory): seq(seq(order(d,n-1), d in divisors(n) minus {1,n}), n=1..60); # Ridouane Oudra, Apr 03 2025

PARI

row(n)={if(n==1, [], my(v=divisors(n)); vector(#v, i, znorder(Mod(v[i], n-1))))} \\ Andrew Howroyd, Mar 23 2021

Formula

Let n and k represent the length of the message and the number of sides of the scytale, respectively, with 1 < k < n. For each k that divides n, T(n,k) is the minimum integer i, 1 < i < n, such that n-1 divides k^i - 1.

T(n,k) = A139366(n-1,k), with k|n and 1 < k < n. - Ridouane Oudra, Apr 03 2025