Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 3 4 5 6 7 8 9 10 11 [12]      все
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Gennadiy Usov, будет детерминизм?
А куда он денется?
31 авг 19, 16:48    [21961193]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Gennadiy Usov, будет детерминизм?
А куда он денется?

А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.
31 авг 19, 16:58    [21961195]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.
Где-то надо черпать информацию...
31 авг 19, 17:20    [21961204]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
mayton
Gennadiy Usov
пропущено...
А куда он денется?

А ты хитрый. Когда тебе надо - очень легко апеллируешь к википедии.

В продолжение детерминизма и куда он денется. Я просто поставлю вопрос.

Какие требования мы выдвинем к датчику случайных чисел?
Можем ли мы его при таком раскладе заменить на последовательность

0..1023

или на последовательность с более длинным шагом?

0,1023,2047,3071....2^1023

Как это повлияет на результат повторного эксперимента? Зачем вообще случайность при полном покрытии?
+
    
    /**
     * Constructs a randomly generated BigInteger, uniformly distributed over
     * the range 0 to (2<sup>{@code numBits}</sup> - 1), inclusive.
     * The uniformity of the distribution assumes that a fair source of random
     * bits is provided in {@code rnd}.  Note that this constructor always
     * constructs a non-negative BigInteger.
     *
     * @param  numBits maximum bitLength of the new BigInteger.
     * @param  rnd source of randomness to be used in computing the new
     *         BigInteger.
     * @throws IllegalArgumentException {@code numBits} is negative.
     * @see #bitLength()
     */
    public BigInteger(int numBits, Random rnd) {
        this(1, randomBits(numBits, rnd));
    }

/**
     * Returns true iff this BigInteger passes the specified number of
     * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
     * 186-2).
     *
     * The following assumptions are made:
     * This BigInteger is a positive, odd number greater than 2.
     * iterations<=50.
     */
    private boolean passesMillerRabin(int iterations, Random rnd) {
        // Find a and m such that m is odd and this == 1 + 2**a * m
        BigInteger thisMinusOne = this.subtract(ONE);
        BigInteger m = thisMinusOne;
        int a = m.getLowestSetBit();
        m = m.shiftRight(a);

        // Do the tests
        if (rnd == null) {
            rnd = ThreadLocalRandom.current();
        }
        for (int i=0; i < iterations; i++) {
            // Generate a uniform random on (1, this)
            BigInteger b;
            do {
                b = new BigInteger(this.bitLength(), rnd);
            } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);

            int j = 0;
            BigInteger z = b.modPow(m, this);
            while (!((j == 0 && z.equals(ONE)) || z.equals(thisMinusOne))) {
                if (j > 0 && z.equals(ONE) || ++j == a)
                    return false;
                z = z.modPow(TWO, this);
            }
        }
        return true;
    }
31 авг 19, 17:34    [21961209]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
В продолжение детерминизма и куда он денется. Я просто поставлю вопрос.
Какие требования мы выдвинем к датчику случайных чисел?
.....
Как я сказал ранее, меня мало интересует датчик случайных чисел.

Почти у всех целых чисел,
имеются остатки по mod, равные 1 (первое условие теста М-Р), и не 1, а много раз.
В результате, почти все из этих чисел, в случае "удачной" комбинации случайных чисел,
можно назвать псевдопростыми.

Поэтому желательно иметь другой принцип поиска остатков по mod.
31 авг 19, 17:59    [21961216]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
Gennadiy Usov
допустим для RSA.

Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.
31 авг 19, 22:09    [21961318]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Dimitry Sibiryakov
Gennadiy Usov
допустим для RSA.
Для "допустим RSA" допустим достаточным тестом будет считаться работоспособность сгенерированного ключа на допустим случайном образце. Это не подтвердит простоту полученных чисел но с некоторым допущением они будут таковыми считаться.
Простоту полученных чисел может подтвердить только алгоритм Эратосфена - полный перебор всех делителей от 3 до ...
1 сен 19, 05:18    [21961378]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 3 4 5 6 7 8 9 10 11 [12]      все
Все форумы / Программирование Ответить