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,1

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.

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

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.

Example

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|  |  |  |  |  |  |
...

Prog

(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(', '));
(PARI) row(n)={if(n==1, [], my(v=divisors(n)); vector(#v, i, znorder(Mod(v[i], n-1))))} \\ Andrew Howroyd, Mar 23 2021

Crossrefs

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

Sequence in context: A354954 A237496 A202690 * A257978 A193358 A214028

Adjacent sequences: A342751 A342752 A342753 * A342755 A342756 A342757

Keyword

nonn,tabf,easy

Author

Rodrigo Panchiniak Fernandes, Mar 20 2021

Status

approved