Тесты на простоту

[kthxbye]

Какие существуют тесты на простоту числа в которых так или иначе задействованы различные системы счисления? Насколько ресурсоемким является перевод крупных чисел в относительно маленькие СС?

[Aritaborian]

А смысел?

[Anton_Peplov]

А что, изменение системы счисления как-то облегчает проверку на простоту? За счет чего?

[Xaositect]

kthxbye в сообщении #1214344 писал(а):

Насколько ресурсоемким является перевод крупных чисел в относительно маленькие СС?

Очевидно, линейная от количества цифр.

[Karan]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

[kthxbye]

Таких тестов нет и не было вообще или же их ресурсоемкость настолько велика, что когда-то еще очень давно от этой идеи отказались и задавать такие вопросы просто глупо?

[venco]

Xaositect в сообщении #1214363 писал(а):

kthxbye в сообщении #1214344 писал(а):

Насколько ресурсоемким является перевод крупных чисел в относительно маленькие СС?

Очевидно, линейная от количества цифр.

Так уж и очевидно?
Мне кажется, это как минимум не проще умножения, т.е. для относительно маленьких - $n^2$, а для очень больших - $n\log n\log\log n$.

[Brukvalub]

kthxbye в сообщении #1214368 писал(а):

когда-то еще очень давно от этой идеи отказались и задавать такие вопросы просто глупо?

От какой идеи отказались? Вы пока никакой идеи не высказали, так что и обсуждать-то нечего. Нельзя же считать за "идею" предложение писАть числа каким-либо иным набором цифр, кроме привычного нам десятичного набора.

[Aritaborian]

(Набор)

Ударение набирается так: & #769; (пробел после амперсанда убрать, всё слитно), сразу после ударяемой буквы. Пример: «писа́ть». Ибо доста́ло.

[svv]

(Brukvalubу на заметку)

Никогда не вспоминаю о чтении пи́сать, пока не встречаю написание писа́ть или писАть. Думаю, и многие другие люди тоже.

[arseniiv]

kthxbye в сообщении #1214368 писал(а):

Таких тестов нет и не было вообще или же их ресурсоемкость настолько велика, что когда-то еще очень давно от этой идеи отказались и задавать такие вопросы просто глупо?

Можно смело утверждать, что не существует сколь-нибудь практичного теста, который нетривиально использует системы счисления, т. е. не как инструмент для проведения операций с ними. Скажем, операции над числами произвольной длины производятся на компьютере как вычисления в системе счисления с основанием $2^L$, где $L$ — длина одного из машинных слов. (А от тестов на простоту как раз есть практическая польза только на большущих числах, не влезающих ни в какое машинное слово целиком.)

[kthxbye]

Ну раз такое дело, что идей никаких нет, то откуда же тогда им, собственно, взяться? Всем большое спасибо за ответы, можно считать, что вопрос исчерпан.

(Оффтоп)

Разве букву назначают заглавной только ради ударения?

[arseniiv]

(Заглавная)

В данном случае других применений не видно.

[mihaild]

(перевод чисел)

venco в сообщении #1214372 писал(а):

Мне кажется, это как минимум не проще умножения, т.е. для относительно маленьких - $n^2$, а для очень больших - $n\log n\log\log n$.

Если степень старого основания делится на новое, то точно легко делается за линейное время. А вот если нет - то надо думать.

[Xaositect]

venco в сообщении #1214372 писал(а):

Мне кажется, это как минимум не проще умножения, т.е. для относительно маленьких - $n^2$, а для очень больших - $n\log n\log\log n$.

Да, Вы правы, что-то я погорячился.