Pytania otagowane jako comp-number-theory

2
Złożoność faktoringu w polach liczbowych
Co wiadomo na temat złożoności obliczeniowej liczb całkowitych faktoringu w ogólnych polach liczbowych? Dokładniej: Nad liczbami całkowitymi reprezentujemy liczby całkowite poprzez ich binarne rozszerzenia. Jakie są analogiczne reprezentacje liczb całkowitych w ogólnych polach liczbowych? Czy wiadomo, że pierwszeństwo nad polami liczbowymi ma postać P lub BPP? Jakie są najbardziej znane …
3
Determinant modulo m
Jakie są znane skuteczne algorytmy do obliczania wyznacznikiem macierzy współczynników całkowitą o ZmZm\mathbb{Z}_m , pierścień reszt modulo mmm . Liczba mmm może nie być liczbą pierwszą, lecz złożoną (więc obliczenia są wykonywane w pierścieniu, a nie w polu). O ile mi wiadomo (czytaj poniżej), większość algorytmów jest modyfikacjami eliminacji Gaussa. …
1
Czy istnieje algorytm kwantowy NC do obliczania GCD?
Z uwagi na jedno z moich pytań dotyczących MathOverflow mam wrażenie, że kwestia dotycząca GCD będąc w vs. P jest zbliżona do kwestii dotyczącej Integer faktoryzacji Będąc w P vs. N P .NCNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}NPNP\mathsf{NP} Czy istnieje coś takiego jak „quantum algorytm” dla GCD jak jest kwantowa wielomian czas ( B Q …
4
Obliczanie funkcji Mobiusa
Funkcja Mobiusa jest zdefiniowana jako μ ( 1 ) = 1 , μ ( n ) = 0, jeśli n ma kwadratowy współczynnik liczby pierwszej , a μ ( p 1 … p k ) = ( - 1 ) k, jeśli wszystkie liczby pierwsze p 1 , … , …
3
Użycie sekwencji de Bruijn do znalezienia liczby całkowitej
Sean Anderson opublikował nieco hacków zawierających algorytm Erica Cole'a, aby znaleźć liczby całkowitej bit w operacjach z mnożeniem i wyszukiwaniem.N v O ( lg ( N ) )⌈ log2)v ⌉⌈log2)⁡v⌉\lceil\log_2 v \rceilN.N.NvvvO ( lg( N) )O(lg⁡(N.))O(\lg(N)) Algorytm opiera się na „magicznej” liczbie z sekwencji De Bruijn. Czy ktoś może wyjaśnić …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.