generate_reverse_numbers_and_fast_bruteforce_x, Python

Language: Layout:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math;										#для работы math.pow()
import random;										#для работы random.randrange()

print("\n\nСтарт программы...")				#Когда программа запущена - вывести это.

# Функция генерация обратных чисел:
def generate_numbers(x, n, start):							#x - число, n - количество чисел, start - стартовое число для генерации массива.
															#В массиве, 2*(n-start) чисел, так как +x и -x для каждого.
	print "\n\nГенерация массива обратных чисел:"
	numbers = [];																		#пустой массив для обратных чисел

max = (n-1).bit_length();															#битовая длина числа (n-1).
	
	bits = 0;																			#биты - в ноль
	for i in range(start, n):															#от start до n
		bits = bin(i)[2::].zfill(max);														#генерируется битовая строка
		#print(bits);

polynom = 0;																			#изначально - ноль.
		for m in range(0, max):																	#для каждого бита в битовой строке.
			polynom = polynom + ( int(bits[m]) * int(n/(int(math.pow(2, max-m)))) )				#добавляю (бит * n/(2^(позиция бита справа))

numbers.append( (n + polynom+x)%n );												#polynom+x -> в массив
		numbers.append( (n + polynom-x)%n );												#polynom-x -> в массив
	print "numbers = ", numbers;														#вывод массива чисел.

#функция поиска x, со встроенной функцией генерации обратных чисел.
def find_x(x, n, start, compare=0):						#x - подбираемое число (это - неизвестное),
														#n - максимальное число итераций (2^N) для подбора x,
														#start - стартовое значение для запуска генератора,
														#compare - число последовательных чисел в массиве, для сравнения на каждой итерации.

print("\n\nЗапуск самого подбора x:");
	max = (n-1).bit_length();							#битовая длина числа (n-1). Если всего 256(10) = 100000000(2),
														#то длина числа 256-1 = 100000000-1 = 255 = 11111111, и длина - 8

compare_array = list(range(compare));					#массив последовательных чисел, для сравнения. Генерируется, и будет висеть в памяти.
	print "compare_array = ", compare_array;				#вывод этого массива, для наглядности.

#Теперь, перебираться будут все биты от числа start до n, или же, пока не будет найдено число x.
	#На основе комбинаций этих бит - будет составлена последовательность чисел,
	#которые в каждой итерации, будут сравниваться со сгенерирванным выше - массивом.
	
	bits = 0;											#изначально, это ноль.
	output = 1;											#выводить столько раундов, чтобы сохранить start, в случае долгой работы программы. С этого start, можно начать в будущем.
	
	for i in range(start, n):							#Начиная со стартового числа, и аж до n, либо пока не будет найдено x
		if(i%output == 0):									#если блок обработан
			print "Проверено чисел =", i;					#вывести число, которое может быть использовано в качестве параметра start.

bits = bin(i)[2::].zfill(max);						#генерируется битовая строка.
		#print(bits);										#тут она - выводится

#Теперь, сгенерирую полином, в зависимости от бит
		polynom = 0;																	#изначально, это - ноль.
		for m in range(0, max):															#для каждого бита битовой строки.
			polynom = polynom + ( int(bits[m]) * int(n/(int(math.pow(2, max-m)))) )			#добавляю к полиному (бит * n/(2^(позиция бита справа))

#Теперь, на каждой итерации, к каждому новому полиному, прибавляется x, и отнимается от него - x.
		#Результат - сравнивается с массивом чисел. Если он там есть, x найдено, оно вычисляется и возвращается.
	
		#прибавлю x
		if(((n + polynom+x)%n) in compare_array):																		#если есть в массиве
			found_x = ( n - (polynom - ((n + polynom+x)%n)) )%n;														#вычислить x
			print "+x, Итерация:", ((i+1)*2-1), "(это порядковый номер числа в массиве выше),", "\n", "number =", ((n + polynom+x)%n), "(само число) - in compare_array,", "found_x =", found_x, "True?", (found_x==x)
																														#вывести инфу
			return found_x;																								#вернуть x
			break;																										#или - остановить цикл
		#иначе, отниму x
		elif(((n + polynom-x)%n) in compare_array):																		#если есть в массиве
			found_x = ( n + (polynom - ((n + polynom-x)%n)) )%n;														#вычислить x
			print "-x, Итерация:", ((i+1)*2), "(это порядковый номер в массиве выше),", "\n", "number =", ((n + polynom-x)%n), "(само число) - in compare_array,", "found_x =", found_x, "True?", (found_x==x)
                                                                                                                        #вывести инфу
			return found_x;																								#вернуть x
			break;																										#или - остановить цикл
		#else:
		#	print("another case");
		#	continue;
	#Конец функции.

#Запуск функции
#Тут, задаются параметры и запускается функция.
compare = 10;											#число чисел в памяти, для сравнения на каждой итерации.
n = int(math.pow(2, 6));								#максимальное число итераций для нахождения x

x = random.randrange(0, n);								#x - генерируется, и лежит в пределах [0, ..., n-1]
print "Сгенерированное x =", x, ", максимальное число для подбора x: ( n = ", n, ")";

#просто сгенерирую - последовательность обратных чисел, в виде массива, и выведу её.
generate_numbers(x, n, 0);	#это массив numbers, с n-числами.

found_x = find_x(x, n, 0, compare);						#подбираемый x; Параметры: x - изначальное число, n - максимальное число комбинаций (2^(max_bitlength_x)),
														#start - start number, compare - число последовательных чисел в памяти.

print "Подобранное x = ", found_x, "True?", (x==found_x);	#вывод найденного x, и сравнение его со сгенерированным x.

[ + ] Show input
Absolute running time: 0.44 sec, cpu time: 0.39 sec, memory peak: 5 Mb, absolute service time: 0,45 sec