Python | Теоретико-обратное преобразование чисел

Теоретико-обратное преобразование чисел - это обобщение теоремы о быстром преобразовании Фурье. Он получается заменой e ^ (- 2piik / N) на n-й примитивный корень из единицы. Это означает, что вместо комплексных чисел C используйте преобразование кольца частных Z / pZ . Теория основана на понятиях конечных полей и теории чисел и использует их.

Модуль преобразования теории обратных чисел обязательно должен быть простым. Но если он простой, это упрощает задачу. Можно выполнить обратную NTT с составным модулем. Для модуля:

• n- ^й корень существования единства
• мультипликативная обратная к n

Теоретико-числовое преобразование - это, по сути, преобразование Фурье . Также предположим, что дано нормальное дискретное преобразование Фурье, и оно может быть выполнено в матричной форме путем умножения данных на матрицу Фурье. Предположим, N = 4. Тогда матрица может быть -

[1 1 1 1]
[1 нед ^ 2 нед ^ 3]
[1 вес ^ 2 вес ^ 4 вес ^ 6]
[1 вес ^ 3 вес ^ 6 вес ^ 9]

sympy.discrete.transforms.intt ():

Он может выполнять обратное теоретико-числовое преобразование (NTT) последовательности. Он специализируется на факторкольце дискретного преобразования Фурье (ДПФ) с Z / pZ для простых чисел вместо комплексных чисел.

Последовательность автоматически дополняется нулем вправо, потому что БПФ по основанию 2 требует, чтобы номер точки выборки был степенью двойки.

Parameters : 
-> seq       : [iterable] sequence on which DFT is to be applied.
-> prime no. : [Integer] prime modulus for INTT to perform on.

Returns : 
Number Theoretic Transform

Example #1 :

Выход :

Обратный NTT: [600, 357, 183, 413]

Example #2 :

Выход :

Обратный NTT: [355, 710, 557, 69]

Внимание компьютерщик! Укрепите свои основы с помощью базового курса программирования Python и изучите основы.

Для начала подготовьтесь к собеседованию. Расширьте свои концепции структур данных с помощью курса Python DS. А чтобы начать свое путешествие по машинному обучению, присоединяйтесь к курсу Машинное обучение - базовый уровень.