Nano Hash - криптовалюты, майнинг, программирование

Перебор отдельных битов в java BigInteger

Я пытаюсь реализовать некоторый математический код Монтгомери для назначения шифрования; У меня большая часть работает, за исключением шага, на котором мне нужно сравнить каждый отдельный бит в BigInteger с One.

Математический алгоритм, который я использовал, начиная с шага 4,

for i = k - 1 down to 0 do
xBar = MonPro(xBar, xBar)
if e[i] = 1 then xBar = MonPro(MBar, xBar)

i — это просто индекс, k — количество битов в BIgInteger, а b — показатель степени. Моя попытка:

for(int i = n.bitLength() - 1; i > 0 ; i--) {
    xBar = monPro(xBar, xBar, r, nPrime, n);
    if (n.testBit(i) == true)
         xBar = monPro(mBar, xBar, r, nPrime, n);
}
return monPro(xBar, BigINteger.ONE, r, nPrime, n);

monPro — это вспомогательная функция, которая определенно работает. Точно так же шаги, пропущенные перед этим фрагментом кода, определенно работают. Итак, главный вопрос заключается в том, как мне побитово перебирать BigInteger? Если я не ошибаюсь насчет e[i], см. ниже.

За последнее время я много читал об этом, и ресурсов мало, что касается реальных реализаций. Некоторые математические статьи, опубликованные на эту тему, носят чисто загадочный характер.

Я также не уверен, что это e [i] выше. В книге это e с маленькой буквой i под ней, точно так же, как Log2 обычно имеет 2, написанную как небольшое число под ней. Кто-нибудь может прояснить?

Я попытался привести BigInteger к строке с основанием 2, создать массив символов и выполнить сравнение с 1 на нем. Я также попробовал просто BigInteger.toString(2), чтобы создать строку с основанием 2 и прокрутить ее, используя charAt[i] == 1.

Я уверен, что все шаги выше e[i] верны, потому что я проверил их с большим количеством различных значений.

Если я не в курсе аспекта E [i], может ли кто-нибудь объяснить, что это на самом деле означает? И если нет, может ли кто-нибудь указать на какие-либо ошибки или небольшое направление?

Это домашнее задание, поэтому не указывайте код, кроме фрагментов.

Любое направление или совет будут очень признательны.

java cryptography bit-manipulation biginteger
01.11.2012

  • Почему bitLength() и testBit() недостаточно для побитовой итерации? Может ли n быть отрицательным? 01.11.2012
  • Я думал, что их должно быть достаточно, Миха, но они не работают в этом контексте. Отсюда мое замешательство. И нет, насколько я знаю, N не может быть отрицательным. 01.11.2012
  • извините за неправильный формат, ниже тестовая программа BigInteger: import java.math.BigInteger; импортировать java.util.Scanner; открытый класс IntegerBits { public static void main (final String [] args) { final Scanner in = new Scanner (System.in); большое целое n; Система.out.print(n =); n = in.nextBigInteger(); в то время как (n.compareTo(BigInteger.ZERO) != 0) { for (int i = n.bitLength(); i › 0; --i) { final char c = (n.testBit(i - 1) == истинный) ? «1»: «0»; Система.выход.печать(с); } System.out.println(); Система.out.print(n =); n = in.nextBigInteger(); } in.close(); } } 01.11.2012
  • @MichaWiedenmann Может быть, вам следует опубликовать это как ответ, конечно, в правильном формате? 01.11.2012
  • @MichaWiedenmann Использование --i в операторе for немного опасно, поскольку оно не делает ничего отличного от i-- и может поставить других разработчиков в неловкое положение. 02.11.2012
  • @owlstead Я предпочитаю --i i--, поскольку i-- может включать временное, а --i либо равно, либо более эффективно, чем i--. 02.11.2012
  • @MichaWiedenmann, я полагаю, это предпочтение программиста. Ваш работает немного лучше, мое предпочтение немного больше склоняется к удобочитаемости :) 02.11.2012

Ответы:


1 
for(int i = n.bitLength() - 1; i > 0 ; i--) { ... }

При этом будет пропущен бит 0 (потому что при i==0 цикл завершается).
Попробуйте использовать >= вместо >:

for(int i = n.bitLength() - 1; i >= 0 ; i--) { ... }

В качестве альтернативы, если вы используете Java 7 и вы знаете, что n является положительным, вы можете преобразовать его в BitSet и перебрать его биты '1':

static void showBitsOf(BigInteger n) {
    if (n.compareTo(BigInteger.ZERO) < 0) {
        throw new IllegalArgumentException("n must not be negative");
    }
    BitSet bs = BitSet.valueOf(n.toByteArray());
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
        System.out.println(i);
    }
}
01.11.2012
  • Почему бы просто не сравнить с ›= 0 ? 01.11.2012
  • @owlstead: вы можете (но этот код будет длиннее моего примера). 01.11.2012
  • По одному персонажу или около того? И разработчики должны хорошо знать цикл for, чтобы знать, что выражение сравнения оценивается раньше, чем часть увеличения. Почему-то я предпочитаю делать приращение/уменьшение в части приращения цикла for. Может быть, потому что он был сделан для этой цели. 02.11.2012
  • @owlstead: я думал, что for (i=N; i-->0;) очень распространенная идиома в C и Java, но, судя по комментариям, многие люди не знакомы с ней. Так что поменяю на >= версию. 02.11.2012
  • это не распространено в моей компании или библиотеках, которые я использую, приятно видеть, что другие люди делают это, даже если это не соответствует моим предпочтениям. Спасибо за изменение. 02.11.2012
  • Большое спасибо за это. Мне удалось реализовать операции Монтгомери, но они оказались медленнее моего исходного бинарного метода справа налево на величину 3! Это нормально или у меня работает но лажает? 04.11.2012
  • Я разместил код на обзоре кода, если кому-то интересно взглянуть на него - codereview.stackexchange.com/questions/18199/ 04.11.2012
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..