cp's OEIS Frontend

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

%I A342754 #67 Apr 08 2025 22:12:49
%S A342754 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,
%T A342754 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,
%U A342754 8,8,10,10,16,16,12,12,6,2,6,12,12,36,36,18,18,12,6,4,4,6,12
%N 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).
%C A342754 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.
%D A342754 Rodrigo Panchiniak Fernandes, OpenPGPjs in Drupal: Practical Privacy-Driven Web Development, Apress (Springer), 2021, 35-40. (in press)
%H A342754 Rodrigo Panchiniak Fernandes, <a href="/A342754/b342754.txt">Table of n, a(n) for n = 1..10000</a>
%H A342754 Rodrigo Panchiniak Fernandes, <a href="https://crypto.stackexchange.com/questions/88431/how-can-i-determine-the-number-of-times-i-have-to-reapply-the-scytale-until-the">Initial question</a>, Cryptography Stack Exchange.
%H A342754 Wikipedia, <a href="https://en.wikipedia.org/wiki/Scytale">Scytale</a>
%F A342754 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.
%F A342754 T(n,k) = A139366(n-1,k), with k|n and 1 < k < n. - _Ridouane Oudra_, Apr 03 2025
%e A342754 Irregular triangle begins:
%e A342754   00|01|02|03|04|05|06|...
%e A342754   01|  |  |  |  |  |  |
%e A342754   02|  |  |  |  |  |  |
%e A342754   03|  |  |  |  |  |  |
%e A342754   04|  | 2|  |  |  |  |
%e A342754   05|  |  |  |  |  |  |
%e A342754   06|  | 4| 4|  |  |  |
%e A342754   07|  |  |  |  |  |  |
%e A342754   08|  | 3|  | 3|  |  |
%e A342754   09|  |  | 2|  |  |  |
%e A342754   10|  | 6|  |  | 6|  |
%e A342754   11|  |  |  |  |  |  |
%e A342754   12|  |10| 5| 5|  |10|
%e A342754   13|  |  |  |  |  |  |
%e A342754   ...
%p A342754 with(numtheory): seq(seq(order(d,n-1), d in divisors(n) minus {1,n}), n=1..60); # _Ridouane Oudra_, Apr 03 2025
%o A342754 (JavaScript)
%o A342754 // m = 1..10000
%o A342754 let n = 0n;
%o A342754 let a = [];
%o A342754 for (let m = 1n; m < 10001n; m = m + 1n){
%o A342754   for (let k = 2n; k <= m; k = k + 1n){
%o A342754     if ((m % k) == 0n){
%o A342754       let xmod = 1n;
%o A342754       for (let x = 1n; xmod != 0n; x = x + 1n){
%o A342754         xmod = ((k ** x) - 1n) % (m - 1n);
%o A342754         if (xmod == 0n && x != 1n){
%o A342754           a[n] = x;
%o A342754           n++;
%o A342754         }
%o A342754       }
%o A342754     }
%o A342754   }
%o A342754 }
%o A342754 console.info(a.join(','));
%o A342754 (PARI) row(n)={if(n==1, [], my(v=divisors(n)); vector(#v, i, znorder(Mod(v[i], n-1))))} \\ _Andrew Howroyd_, Mar 23 2021
%Y A342754 Row n is contained in row n-1 of A216327.
%Y A342754 Cf. A139366.
%K A342754 nonn,tabf,easy
%O A342754 1,1
%A A342754 _Rodrigo Panchiniak Fernandes_, Mar 20 2021