Обсуждение:Безопасное простое число

Демонстрация и доказательство представления безопасных чисел в виде q=6k-1, q=3k-1, и q=12k-1

Представление безопасного числа q в виде формулы q = 6k-1, или же, что эквивалентно q ≡ 5 (mod 6), или же как критерий проверки - (5 = q mod 6, q>7),

может быть проверено, вот таким вот образом. Доказательство - в комментарии кода:

JavaScript : https://jsfiddle.net/1zpvyos8/

Код

//check is safe primes (q === 5 (mod 6)) or ( (5 === q mod 6) === true )

var x = [
//Safe primes
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903 /*, etc...*/
];

//check is (x[i] mod 6 === 5) false?
for(var i = 0; i<x.length; i++){
	if( (x[i] % 6) !== 5 ){ //if false
  	eval(//run
    	document.write( //print of this
  			' i: '+i+//show i
  	  	' prime: '+x[i]+ //show prime
  	  	' ( (x[i] % 6) === 5 ) '+((x[i] % 6) === 5 )+ //show false
      	'<br>' //add next line
 	  	)
    );
  }else{//if (x[i] mod 6 === 5) === true
  	continue; //do nothing, and continue checking next safe prime
  }
}

/*
Попробую сам доказать, справедливость представления безопасного числа q в виде формулы q = 6k-1,
или же, что эквивалентно q ≡ 5 (mod 6), или же как критерий проверки - (5 = q mod 6, q>7).

Пусть q = 6k + r, где k - целое натуральное, а r = (q % 6) - число в диапазоне [0, ..., 5] , а именно числа 0,1,2,3,4,5 - соответственно.
Любое число, представимо в этом виде, как впрочем и в виде (q = m*k + r), где m - произвольный множитель, k - второй множитель, r = q%m - остаток от деления.
Но нам нужные безопасные простые числа.

Четные значения r = 2x (а именно, r = 0,2,4, при x = 0,1,2) - исключаются сразу, так как (6k + 2x) = 2*(3k + x),
а значит число делится на два - число чётное, а не нечётное, коим является - безопасное простое и любое простое.

r = 3 - также исключается, поскольку при q = (6k + 3) = 3*(2k + 1) - делится на 3, при любом k, а простое число не делится ни на что, особенно безопасное.

r = 1, также исключается, поскольку при (q = 6k + 1), q-1 = 6k = 2*3k, следовательно, (q-1)/2 = 3*k, а значит, делится на 3, и не является простым числом Софи-Жермен.
Следовательно, q - не является безопасным простым, при любом k.
Исключение составляет k=1 (q = 6k+1 = 6*1+1 = 7), ведь в этом случае, число (7-1)/2 = 3, оно хоть и делится на 3,
но оно делится на себя же, и являясь при этом - простым числом Софи-Жермен, следовательно q = 7 - безопасное простое число.

Итак, из возможных значений r, среди 0,1,2,3,4,5, были исключены 5 чисел - 0,1,2,3,4, и единственное возможное значение - это 5.
Следовательно, безопасное простое, может быть представлено в виде q = 6k+5.
Пусть теперь, y = k; а k = y+1;
Тогда, q = 6y+5 = 6(y+1)-1 = 6k-1.
Изначальное утверждение доказано.
*/

Аналогичный результат проверки, можно видеть и для доказанного (в комментарии кода)

представления любого безопасного простого числа q

в виде q = 4k − 1, или q ≡ 3 (mod 4), или же как критерий - (3 = q mod 4, q>5):

JavaScript : https://jsfiddle.net/o5v1qgn4/

Код

//check is safe primes (q === 3 (mod 4)) or ( (3 === q mod 4) === true )

var x = [
//Safe primes
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903 /*, etc...*/
];

//check is (x[i] mod 4 === 3) false?
for(var i = 0; i<x.length; i++){
	if( (x[i] % 4) !== 3 ){ //if false
  	eval(//run
    	document.write( //print of this
  			' i: '+i+//show i
  	  	' prime: '+x[i]+ //show prime
  	  	' ( (x[i] % 4) === 3 ) '+((x[i] % 4) === 3 )+ //show false
      	'<br>' //add next line
 	  	)
    );
  }else{//if (x[i] mod 4 === 3) === true
  	continue; //do nothing, and continue checking next safe prime
  }
}

/*
Покажем, что безопасное простое, представимо в форме q = 4k - 1.
Пусть x = k-1, тогда, k = x+1; q = 4 * (x+1) - 1 = 4x + 3.

Теперь рассмотрим ряд натуральных чисел:
4 * x + r = q		- критерий: q должно быть нечётным, таким, чтобы ((q - 1)/ 2) было тоже нечётным.
______________________________________________________________________________________________________
4 * 0 + 0 = 0		false: четное
4 * 0 + 1 = 1		false: нечётное - 1 = 0 / 2 = 0 - четное
4 * 0 + 2 = 2		false: четное
4 * 0 + 3 = 3		true (r = 3): нечётное - 1 = 2 / 2 = 1 - нечётное
4 * 1 + 0 = 4		false: четное
4 * 1 + 1 = 5		false: нечётное - 1 = 4 / 2 = 2 - четное
4 * 1 + 2 = 6		false: четное
4 * 1 + 3 = 7		true (r = 3): нечётное - 1 = 6 / 2 = 3 - нечётное
4 * 2 + 0 = 8		false: четное
4 * 2 + 1 = 9		false: нечётное - 1 = 8 / 2 = 4 - четное
4 * 2 + 2 = 10		false: четное
4 * 2 + 3 = 11		true (r = 3): нечетное - 1 = 10 / 2 = 5 - нечетное
4 * 3 + 0 = 12		false: четное
4 * 3 + 1 = 13		false: нечетное - 1 = 12 / 2 = 6 - четное
4 * 3 + 2 = 14		false: четное
4 * 3 + 3 = 15		true (r = 3): нечетное - 1 = 14 / 2 = 7 - нечетное
4 * 4 + 0 = 16		false: четное
4 * 4 + 1 = 17		false: нечетное - 1 = 16 / 2 = 8 - четное
4 * 4 + 2 = 18		false: четное
4 * 4 + 3 = 19		true (r = 3): нечетное - 1 = 18 / 2 = 9 - нечетное
4 * 5 + 0 = 20		false: четное
... и т. д.

Так как остаток (q mod 4) = r = 3, всегда, там где критерий === true,
значит q = 4*x + 3 или же q = 4*(x+1) - 1 = 4k - 1;
Утверждение показано.

Доказательство:
Пусть q = 4 * x + r; x - натуральное число, r = q mod 4 - число от 0 до 3 (0,1,2,3). Так, можно представить - любое натуральное.
1. Исключаем четные r = 2*y, а именно (r = 0, при y = 0, и r = 2 при y = 1), так как q = 4x+r = 4*x + 2y = 2*(2x+y),
и в этом случае q не простое (нечётное), а чётное, и не простое.

2. Исключаем r = 1, так как при q = (4k + 1), (q-1) = 4k, (q-1)/2 = 2*k, а значит делится на 2, и не является нечётным простым числом Софи-Жермен, значит q - не безопасное простое.
Исключение: k = 1, q = 4*k + 1 = 4*1+1 = 5 - безопасное простое, с его числом (q-1/2) = (5-1/2) = (4/2) = 2 делящимся само на себя,
и являющимся при этом - простым числом Софи-Жермен.

Итак, из чисел 0,1,2,3 были исключены 0,1,2, а значит r = 3, для безопасного простого, представимого в виде q = 4*x+3; 
Пусть теперь, k = x+1; q = 4*x + 3 = 4*(x+1) - 1 = 4k-1;
Следовательно, безопасное простое, представимо в виде q = 4k - 1;
Изначальное утверждение - доказано.
*/

Следующее, комбинированное утверждение, также доказано (доказательство в комментарии кода).

А именно - представление числа в виде q = 12k−1 , или же что эквивалентно q ≡ 11 (mod 12), или же как критерий проверки (11 = q mod 12, q>7).

Код проверки истинности утверждения сего:

JavaScript : https://jsfiddle.net/vpfw81sj/

Код

//check is safe primes (q === 11 (mod 12)) or ( (11 === q mod 12) === true )

var x = [
//Safe primes
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903 /*, etc...*/
];

//check is (x[i] mod 12 === 11) false?
for(var i = 0; i<x.length; i++){
	if( (x[i] % 12) !== 11 ){ //if false
  	eval(//run
    	document.write( //print of this
  			' i: '+i+//show i
  	  	' prime: '+x[i]+ //show prime
  	  	' ( (x[i] % 12) === 11 ) '+((x[i] % 12) === 11 )+ //show false
      	'<br>' //add next line
 	  	)
    );
  }else{//if (x[i] mod 12 === 11) === true
  	continue; //do nothing, and continue checking next safe prime
  }
}

/*
Доказательство справедливости представления безопасного простого числа, как q = 12*k - 1:

Пусть q = 12*x+r; где x - натуральное число, r = q%12 - остаток от деления на 12, а именно число со значением от 0 до 11 (0,1,2,3,4,5,6,7,8,9,10,11).
Таким образом, может быть представлено любое натуральное.

Теперь, докажем, справедливость представления произвольного натурального как q = 12*x+11:
При r = 0; q = 12*x + 0 = 12*x - делится на 12 и не является простым.
При r = 1; q = 12*x + 1; (q-1)/2 = 12*x/2 = 6*x - делится на 6 и не является простым числом Софи-Жермен.
При r = 2; q = 12*x + 2; q = 2*(6x+1) - делится на 2, четное, не является нечётным, коим является любое простое, а значит это - не простое число.
При r = 3; q = 12*x + 3; q = 3*(4x+1) - делится на 3, и не является простым, так как простое делится только на себя и на 1, а не на что-то другое.
При r = 4; q = 12*x + 4; q = 2*(6x+2) - делится на 2, четное, не является нечётным, коим является любое простое, а значит это - не простое число.
При r = 5; q = 12*x + 5; (q-1)/2 = (12*x+4)/2 = 2*(6x+2)/2 = (6x+2) = 2*(3x+1) - а значит делится на 2, и чётное, и не является простым (нечётным).
	Исключение здесь: x = 0; q = 12*0 + 5 = 5; (q-1)/2 = (5-1)/2 = 4/2 = 2, хоть и чётное, но простое число Софи-Жермен, так как делится на себя и на 1.
При r = 6; q = 12*x + 6; q = 2*(6x+3) - делится на 2, четное, не является нечётным, коим является любое простое, а значит это - не простое число.
При r = 7; q = 12*x + 7; (q-1)/2 = (12*x+6)/2 = 2*(6x+3)/2 = (6x+3) = 3*(2x+1) - а значит делится на 3, и не является простым числом Софи-Жермен, которое делится только на себя и 1, а не на что-то другое.
Исключение здесь: x = 0; q = 12*0 + 7 = 7; (q-1)/2 = (7-1)/2 = 6/2 = 3, хоть и делится на 3, но простое число Софи-Жермен, так как делится на себя и на 1.
При r = 8; q = 12*x + 8; q = 2*(6x+4) - делится на 2, четное, не является нечётным, коим является любое простое, а значит это - не простое число.
При r = 9; q = 12*x + 9; (q-1)/2 = (12*x+8)/2 = 2*(6*x+4)/2 = (6x+4) = 2*(3x+2) - а значит делится на 2, и чётное, и не является простым (нечётным).
При r = 10; q = 12*x + 10; q = 2*(6x+5) - делится на 2, четное, не является нечётным, коим является любое простое, а значит это - не простое число.

Итак, из возможных значений r = q%12, из чисел 0,1,2,3,4,5,6,7,8,9,10,11,
были исключены (с одним ислключением) числа значения r = 0,1,2,3,4,5,6,7,8,9,10, остаётся только число 11.
Следовательно, r = 11, и безопасное простое число, может быть представлено в виде q = 12*x + 11;
Пусть теперь, k = (x+1); q = 12*(x+1) - 1 = 12k - 1;
q = 12k - 1.
Изначальное утверждение - доказано.

*/

Просто оставлю это здесь, чтобы не флудить в основной статье.

213.231.62.76 11:44, 15 октября 2020 (UTC)