ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
25 сообщений из 283, страница 4 из 12
  4  все
Ещё раз о тесте Ферма
    #39843789
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Продолжил построение различных множеств простых чисел.

В сообщениях 21908344 и 21913903 говорилось о построении одного из таких множеств.

Можно построить одно из подмножеств данного множества: простые числа после 2^198.

В результате за 0,7 секунд на компьютере определились 64 числа, большие 2^198 на следующие величины:

277, 693, 763, 1165, 1395, 1723, 2157, 2349, 2613, 3067, 3397, 3637, и т.д.

Эти числа проверены на факторизаторе чисел.
...
Рейтинг: 0 / 0
01.08.2019, 07:28
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39844469
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Так никто не ответил на первое сообщение топика:
"А кроме чисел Мерсенна есть ли ещё примеры «ошибочности» теста Ферма?"

Покопался в вики и нашел:
https://ru.wikipedia.org/wiki/Псевдопростое_число

Существует последовательность A001567 в https://oeis.org/A001567

где есть числа:
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681,
5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491,
15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341

2047 - число Мерсенна
3277, 29341 - из сообщения 21908370

В эту последовательность войдут все составные числа Мерсенна - Мр, у которых р - простое число.
...
Рейтинг: 0 / 0
02.08.2019, 10:25
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39844578
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
А далее - самое интересное!

Во многих науках решается не прямая задача (в нашем случае определение простых чисел),
а обратная задача - рассмотрение случаев "сбоев" в решении прямой задачи.

Например, есть тест Ферма, и у этого теста есть "сбои", пусть немного, но есть.
Что не позволяет "доверять" тесту Ферма для всех случаев.

Если получится понять поведение последовательности 21940432 ,
то задача определения простых чисел с помощью теста Ферма (и ещё чего-нибудь) будет решена.
...
Рейтинг: 0 / 0
02.08.2019, 12:44
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39844918
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Решил сам определить последовательность чисел,
полученных в результате «ошибочности» теста Ферма.

За 4 сек. нашел 148 чисел из первых 500000 чисел, начиная с 1.
Шаг был, начиная с 1, сначала 4, затем 2, затем 4, и т.д.

Получилось, что при шаге 2 получилось 123 составных числа.
А при шаге 4 получилось 25 составных чисел.

В последовательности 21940432 рассматривались все нечётные числа.
В этом случае получается 172 составных числа.
...
Рейтинг: 0 / 0
03.08.2019, 12:55
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39845430
ёёёёё
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ёёёёё
Участник
Barlone...RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.

Числа есть, а хранить их негде. Бардак.
...
Рейтинг: 0 / 0
05.08.2019, 15:27
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39845452
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
ёёёёёBarlone...RSA шифрование. Числа там нужны от 2^1024. Даже если бы удалось придумать, как получить список, его негде хранить - количество элементарных частиц и видимой части вселенной сильно меньше, чем нужное количество элементов списка.Числа есть, а хранить их негде. Бардак.А зачем хранить?

Если есть такое хранилище, то оно доступно как криптографикам, так и криптоаналитикам.
...
Рейтинг: 0 / 0
05.08.2019, 16:03
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39845478
ёёёёё
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ёёёёё
Участник
Gennadiy Usovёёёёёпропущено...
Числа есть, а хранить их негде. Бардак.А зачем хранить?

Если есть такое хранилище, то оно доступно как криптографикам, так и криптоаналитикам.
В параллельной вселенной?
...
Рейтинг: 0 / 0
05.08.2019, 17:09
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39845532
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
ёёёёёGennadiy UsovА зачем хранить?
Если есть такое хранилище, то оно доступно как криптографикам, так и криптоаналитикам.В параллельной вселенной? Зачем так далеко забираться?

Малые простые числа - не интересны. Их можно найти в реальное время.

Представляют интерес простые числа, связанные с криптографикой.

Поскольку на имеющихся ЭВМ, в реальное время, можно найти очень небольшое количество простых чисел,
"пригодных" для криптографии, то и воображаемая библиотека найденных больших простых чисел будет небольшой.

В реальности представляет интерес разработка программ,
позволяющих определять простые числа на "высоте" чисел 2^1024 или на "высоте" 2^2048.

Например, поиск простых чисел, аналогичный поиску 21939419
...
Рейтинг: 0 / 0
05.08.2019, 18:07
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39847894
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy UsovmaytonМне кажется что вероятностные тесты простоты мы уже обсуждали.А если для вероятностного теста простоты появляется дополнительное условие?
Которое определяет достаточность теста простоты?Что за условия? Как вы их найдете?Просто никто не рассматривал составные числа, которые "проходят" тест Ферма.
Этих чисел немного, поэтому их можно анализировать.

Для начала - 21940591
...
Рейтинг: 0 / 0
11.08.2019, 09:31
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39847952
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonЕсть статья которая описывает библиотеку SymPy

https://www.geeksforgeeks.org/prime-functions-python-sympy/ Просьба: можно получить часть кода, где эта библиотека подключается.

Например, вместе с isprime (n)
...
Рейтинг: 0 / 0
11.08.2019, 16:37
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39849420
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Важно рассмотреть ещё один вопрос.

В сообщении 21939419 говорилось о найденной последовательности простых чисел.

Допустим, на отрезке от 2^1023 до 2^1023 + 10000000 на домашнем компьютере за несколько минут
найдено несколько простых чисел.

Насколько полученная последовательность простых чисел может помочь
в решении задачи поиска простых чисел в районе 2^1024?
...
Рейтинг: 0 / 0
14.08.2019, 18:17
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39849501
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Первые несколько штук (probable prime).

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989
...
Рейтинг: 0 / 0
14.08.2019, 21:38
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39849572
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonПервые несколько штук (probable prime).

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989

И сколько времени ушло на поиск этих чисел?
И с помощью какого теста простоты?
...
Рейтинг: 0 / 0
15.08.2019, 07:16
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39849597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Несколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.

Но в JDK-11 как мне показалось поменялся исходных код этого теста. Я где-то привдил сорцы с 8 версии
там отчотливо был видел тест Люка в совокупности с Миллером. Сейчас я не дам гарантий. Надо смотреть и изучать.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
import java.math.BigInteger

object Main {

  def bigPower(x : Int, y : Int) : BigInt = {
    var product : BigInt = 1
    for(k <- 1 to y) {
      product = product * x
    }
    product
  }

  def main(arg : Array[String]) : Unit = {
    val x : BigInt = bigPower(2, 1023)
    var javaBigint = new BigInteger(x.toString(10))
    javaBigint = javaBigint.nextProbablePrime()
    do {
      javaBigint = javaBigint.nextProbablePrime()
      println(javaBigint)
      println(" ")
    } while(javaBigint.compareTo( x + BigInt(2000)) < 0) // while(javaBigInt < x + 2000) 

  }

}



Еще есть забавный косяк. Я написал за пару минут функцию bigPower для встроенного в Scala типа BigInt, полагая
что это бридж к java-шному BigInteger. Дальше обнаружил что bigInt не работает с функциями простоты и добавил
java-шный тип BigInteger. Поэтому в исходнике есть два разных типа от двух разных языков.
...
Рейтинг: 0 / 0
15.08.2019, 09:28
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39849599
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Щас качнул снова зеркало исходников JDK чтоб посмотреть историю.
...
Рейтинг: 0 / 0
15.08.2019, 09:41
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39849616
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Второте и третье число - близнецы кстати.
...
Рейтинг: 0 / 0
15.08.2019, 10:29
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850019
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonНесколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.А есть ли такая же программа на питоне?
...
Рейтинг: 0 / 0
15.08.2019, 19:48
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850524
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonПервые несколько штук (probable prime).

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070101
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070191
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070293
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070471
 
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112070989

Было бы интереснее по другому представить информацию по поиску простых чисел (пример - 21939419 ):
в начале - исходное число, лучше в виде 2^1023 (именно так!),
а далее - разность между очередным простым числом и исходным числом.

Так более читаемо.
И можно зрительно отследить интервалы между найденными простыми числами.
...
Рейтинг: 0 / 0
16.08.2019, 18:35
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850589
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovmaytonНесколько секунд. Тест - вероятностный. Стандартный BigInteger::nextProbablePrime.А есть ли такая же программа на питоне?
Я не специалист в Питоне. Но я думаю что тест Люка и Ребе-Миллера там должен быть. И длинная арифметика должна тоже
быть.

Есть Питонщики?
...
Рейтинг: 0 / 0
16.08.2019, 23:03
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850595
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
518
282
78
1212
772
1298
826
212
654
258
750
22
264
1020
84
168
600
554
168
340
450
1190
1030
260
366
2094
3222
...
Рейтинг: 0 / 0
16.08.2019, 23:24
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850623
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
mayton2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.
Код: sql
1.
2.
3.
4.
5.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178

Насколько я понял, здесь показаны расстояния между числами.

В дальнейшем, было бы удобнее вести отсчет от первого числа, чтобы показать числовой ряд.

Например: 2^1023, 1155, 1463,1553, 1655,1833 и т.д.

или
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
428
530
708
1226 и тд.

Спасибо за информацию!
...
Рейтинг: 0 / 0
17.08.2019, 06:30
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850730
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В префиксном коде.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
(8(9(8(8(4(6(5(6(7(4(3(1(1(5(7(9(5(3(8(6(4(6(5(2(5(9(5(3(9(4(5(1(2(3(6(6(8(0(8(9(8(8(4(8(9(4(7(1(1(5(3(2(8(6(3
(6(7(1(5(0(4(0(5(7(8(8(6(6(3(3(7(9(0(2(7(5(0(4(8(1(5(6(6(3(5(4(2(3(8(6(6(1(2(0(3(7(6(8(0(1(0(5(6(0(0(5(6(9(3(9
(9(3(5(6(9(6(6(7(8(8(2(9(3(9(4(8(8(4(4(0(7(2(0(8(3(1(1(2(4(6(4(2(3(7(1(5(3(1(9(7(3(7(0(6(2(1(8(8(8(8(3(9(4(6(7
(1(2(4(3(2(7(4(2(6(3(8(1(5(1(1(0(9(8(0(0(6(2(3(0(4(7(0(5(9(7(2(6(5(4(1(4(7(6(0(4(2(5(0(2(8(8(4(4(1(9(0(7(5(3(4
(1(1(7(1(2(3(1(4(4(0(7(3(6(9(5(6(5(5(5(2(7(0(4(1(3(6(1(8(5(8(1(6(7(5(2(5(5(3(4(2(2(9(3(1(4(9(1(1(9(9(7(3(6(2(2
(9(6(9(2(3(9(8(5(8(1(5(2(4(1(7(6(7(8(1(6(4(8(1(2(1(1(2(0(7(0(1(0(1)9(1))2(9(3))4(7(1))9(8(9)))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

)
...
Рейтинг: 0 / 0
17.08.2019, 23:49
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850789
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
mayton2^1023 - это составное число. Я его писать не буду. Но дельта-кодирование будет выглядеть так.
Лет несколько назад в топике простых чисел мы обсуждали дельта-кодирование для оптимального
хранения. Но сегодня в нас... хранение primes - маветон. Негде хранить это. Хотя концептуально
я придумывал и выбрасывал десяток идей.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112069763
338
90
102
178
518
282
78  и т.д

Но это всё числа, полученные с помощью теста Ферма.

А если среди них есть составные числа, как иногда бывает с тестом Ферма?
...
Рейтинг: 0 / 0
18.08.2019, 12:49
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850804
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Не знаю. Как это проверить?
...
Рейтинг: 0 / 0
18.08.2019, 13:42
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39850812
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Исходный код который (предположительно) работает. Я использую JDK-11.
Исходники брал от OpenJDK. Текущая версия мастер-бранча примерно ей
соответсвует. Я говорю это просто просмотрев активность по изменениям
в модуле BigInteger. Этот модуль стабилен и менялся редко. Особенно в части алгоритма.
Основную его (ядерную часть) закоммитил некто Duke в 2007 году.

Я кажется уже где-то его постил. Запощу еще раз.

Специально для вас прокомментирую. Текущее число это "this". Это функция которая проверяет
объект (метод объекта). Поэтому если вы проверяете число к пример 1999987 то
следует читать this.add(ONE) как 1999987 + ONE или 1999987 + 1.

Здесь ONE, TWO просто константы типа длинное целое. Такой вот он некрасивый язык Java при работе
с объектными (не примитивными) типами.

 

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
    public BigInteger nextProbablePrime() {
        if (this.signum < 0)
            throw new ArithmeticException("start < 0: " + this);

        // Handle trivial cases
        if ((this.signum == 0) || this.equals(ONE))
            return TWO;

        BigInteger result = this.add(ONE);

        // Fastpath for small numbers
        if (result.bitLength() < SMALL_PRIME_THRESHOLD) {

            // Ensure an odd number
            if (!result.testBit(0))
                result = result.add(ONE);

            while (true) {
                // Do cheap "pre-test" if applicable
                if (result.bitLength() > 6) {
                    long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
                    if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
                        (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
                        (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                        result = result.add(TWO);
                        continue; // Candidate is composite; try another
                    }
                }

                // All candidates of bitLength 2 and 3 are prime by this point
                if (result.bitLength() < 4)
                    return result;

                // The expensive test
                if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                    return result;

                result = result.add(TWO);
            }
        }


 
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
    boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

        // The relationship between the certainty and the number of rounds
        // we perform is given in the draft standard ANSI X9.80, "PRIME
        // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
        int sizeInBits = this.bitLength();
        if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return passesMillerRabin(rounds, random);
        }

        if (sizeInBits < 256) {
            rounds = 27;
        } else if (sizeInBits < 512) {
            rounds = 15;
        } else if (sizeInBits < 768) {
            rounds = 8;
        } else if (sizeInBits < 1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }
        rounds = n < rounds ? n : rounds;

        return passesMillerRabin(rounds, random) && passesLucasLehmer();
    }

...
Рейтинг: 0 / 0
18.08.2019, 14:44
| Ответить | Цитировать | Написать  
25 сообщений из 283, страница 4 из 12
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39849501&tid=1339906]:
 0ms
get settings:
 11ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 191ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 69ms
get tp. blocked users:
 1ms
others: 12ms
total:  321ms
созд. / загр.: 321ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]