2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Сколько таких чисел ?
Сообщение04.04.2007, 12:40 


04/04/07
19
Здаствуйте уважаемые посетители форума. Сколько существует таких целых чисел , что при делении произвольного квадрата на эти числа,всегда будет в остатке квадрат? То-же самое для кубов и тд.?

 Профиль  
                  
 
 
Сообщение05.04.2007, 08:57 


23/01/07
3415
Новосибирск
Я не понял вопрос...

 Профиль  
                  
 
 
Сообщение05.04.2007, 08:57 
Заслуженный участник
Аватара пользователя


11/01/06
3822
И что тут дискуссионного?
Вопрос можно сформулировать так: Для каких натуральных $m$ все вычеты степени $d$ по модулю $m$ исчерпываются вычетами $0,1,2^d,\ldots,(\lceil m^{1/d}\rceil-1)^d$, т.е. их кол-во равно $\lceil m^{1/d}\rceil$?
Для $m=p^{\alpha}$, $p~-$ нечётное простое, количество вычетов степени $d$, которые взаимно просты с $p$, равно $\frac{p^{\alpha-1}(p-1)}{(d,p^{\alpha-1}(p-1))}$, что больше $\lceil p^{\alpha/d}\rceil$, если $p$ достаточно велико либо если велико $\alpha$ (при фиксированном $d$).
Для $m=2^{\alpha}$, $\alpha\geqslant3$, количество нечётных вычетов степени $d$ равно $\frac2{(d,2)}\cdot\frac{2^{\alpha-2}}{(d,2^{\alpha-2})}$, что больше $\lceil 2^{\alpha/d}\rceil$ при достаточно большом $\alpha$.
Учитывая еще вычеты степени $d$, которые не взаимно просты с $m$, оценки на $\alpha$ можно уменьшить.
Если $p^{\alpha}||m$ ($p~-$ произвольное простое), причём количество вычетов степени $d$ по модулю $p^{\alpha}$ больше $\lceil p^{\alpha/d}\rceil$, то и для $m$ количество их больше $\lceil m^{1/d}\rceil$ (это достаточное, но не необходимое условие). Это позволяет свести вопрос к конечному перебору для каждого фиксированного $d$.
Например, при $d=2\quad m$ может делиться лишь (пишу по памяти, поэтому неуверен) на $2$ в степени не выше четвёртой и $3,5,7$ в степенях не выше первой. Осталось отсеять лишнее, но это я уже не считал.

 Профиль  
                  
 
 Сколько таких чисел ?
Сообщение05.04.2007, 10:32 


04/04/07
19
Спасибо за Ваши ответы и извините за коряво сформулированный вопрос.Если можно я уточню так. Например любой квадрат при делении на числа 1,2,3,4,5,8,12,16 будет давать в остатке квадраты. Любой куб при делении на 1,2,9 , в остатке дает кубы. Четвертые степени , при делении на 1,2,3,4,5,8,16 - в остатке дают четвертые степени(только 0 или 1). А вопрос - найдутся-ли другие числа обладающие этими свойствами? Интуитивно кажется что нет , но доказать это не получается(ну тупой я ,тупой ,только не бейте :D ). Конечно , как и многие , пытаясь найти "самый" быстрый :) метод факторизации чисел , я и обнаружил этот , на мой взгляд интересный , факт. А с факторизацией это может быть связано следующим образом (опять же интуитивно кажется): при заданном числе А , подлежащим факторизации , найти соответствующие остатки от приделения на 3,4,5,8,12,16 ... и затем найти такой минимальный квадрат , который в сумме с получеными остатками даст при делении опять же на 3,4,5,8,12,16 ... остатки являющиеся квадратами. Например :
Пусть А=161:
тогда при делении на
3,4,5,8,12,16 остатками будут
2,1,1,1,5,1 соотвественно
тогда таким минимальным квадратом будет 64
т.е.
64+2,64+1, 64+1, 64+1, 64+5, 64+1 при делении на
3 ,4 ,5 ,8 , 12 , 16 соответственно ,дают в остатке квадраты. Таким образом 161+64 =225.
Возможно нужно использовать какую-нибудь суперпозицию от 1,2 3,4,5,8,12,16 ...
В этом и есть на мой взгляд предмет дискуссии , если конечно кому нибудь кроме меня это кажется интересным :?
Еще раз спасибо за проявленное внимание.

 Профиль  
                  
 
 
Сообщение05.04.2007, 10:43 
Заслуженный участник
Аватара пользователя


11/01/06
3822
VladimirVK писал(а):
найдутся-ли другие числа обладающие этими свойствами?

Для квадратов любое такое число обязано иметь вид $m=2^{\alpha_0}3^{\alpha_1}5^{\alpha_2}$, где $0\leqslant\alpha_0\leqslant4$, $0\leqslant\alpha_1\leqslant1$, $0\leqslant\alpha_2\leqslant1$ (но не каждое такое годится). Скорее всего, Вы перечислили их все.

 Профиль  
                  
 
 Сколько таких чисел ?
Сообщение05.04.2007, 11:09 


04/04/07
19
Ну-да ,мне тоже так кажется. Контрпример 240 . Но статок от деления 324 на 240 есть 84 - не квадрат. Но вот доказательство ...

 Профиль  
                  
 
 
Сообщение05.04.2007, 11:13 
Заслуженный участник
Аватара пользователя


11/01/06
3822
VladimirVK писал(а):
Но вот доказательство ...

приведено в моём самом первом сообщении. Чтобы его понять, надо знать некоторые сведения из элементарной теории чисел. Можете принять это утверждение на веру.

 Профиль  
                  
 
 Сколько таких чисел ?
Сообщение05.04.2007, 11:39 


04/04/07
19
Спасибо ,обязательно приму на веру и пойму Ваше доказательство. Просто меня смутило Ваше -"(но не каждое такое годится)"...

 Профиль  
                  
 
 
Сообщение05.04.2007, 11:44 
Заслуженный участник
Аватара пользователя


11/01/06
3822
VladimirVK писал(а):
Просто меня смутило Ваше -"(но не каждое такое годится)"...

Легко доказывается, что $m$ обязано иметь такой вид, т.е. все другие заведомо не годятся. Но не все числа указанного вида годятся, для них надо просто отдельно проверить, удовлетворяют ли они условию (их немного, так что это нетрудно).

 Профиль  
                  
 
 Сколько таких чисел ?
Сообщение05.04.2007, 12:01 


04/04/07
19
Merci beaucoup! Теперь все ясно.
P.S.
Извините , я еще не разобрался с использованием тэгов , поэтому и формулировал словами.Обязательно исправлюсь :D

 Профиль  
                  
 
 Re: Сколько таких чисел ?
Сообщение01.02.2008, 07:23 
Модератор
Аватара пользователя


11/01/06
5660
VladimirVK писал(а):
Конечно , как и многие , пытаясь найти "самый" быстрый :) метод факторизации чисел , я и обнаружил этот , на мой взгляд интересный , факт. А с факторизацией это может быть связано следующим образом (опять же интуитивно кажется): при заданном числе А , подлежащим факторизации , найти соответствующие остатки от приделения на 3,4,5,8,12,16 ... и затем найти такой минимальный квадрат , который в сумме с получеными остатками даст при делении опять же на 3,4,5,8,12,16 ... остатки являющиеся квадратами.

А зачем вам при таком подходе нужны именно остатки являющиеся квадратами как целые числа? Как я понял, вам всего лишь необходимо проверять может ли данный остаток быть получен от деления квадрата или нет. Но на этот вопрос есть простой ответ, особенно если остатки рассматриваются от деления на простое число (заметьте, любое простое!) - а именно он дается символом Лежандра.

Теперь по существу метода как такового. Если представить $N$ в виде разности квадратов, скажем $N=x^2-y^2$, то $x$ и $y$ будут порядка величины $\sqrt{N}$. Например, в случае ala RSA для $N=pq$ с $1<p<q<N$ нетривиальное разложение единственно: $N=\left(\frac{p+q}{2}\right)^2 - \left(\frac{q-p}{2}\right)^2$.
Предположим теперь, что вы хотите найти $x$ и $y$ по модулям маленьких простых $p_1, \dots, p_k$, а затем получить и сами числа с помощью китайской теоремы об остатках. Чтобы гарантировать восстановление $x,y$ по их остаткам от деления на выбранные простые нужно, чтобы произведение этих простых было больше $\sqrt{N}$ (в примере с RSA это непосредственно вытекает из неравенства о средних: $x=\frac{p+q}{2}>\sqrt{pq}=\sqrt{N}$). Теперь прикинем объем вычислений.
По модулю каждого простого $p_i$ имеется около $p_i/2$ различных остатков являющихся квадратами, и поэтому сравнение $x^2-y^2\equiv N\pmod{p_i}$ будет в среднем иметь около $p_i/4$ решений $(x,y)$. Таким образом, суммарно придется перебрать и скомпоновать по китайской теореме об остатках около $\frac{p_1}{4}\frac{p_2}{4}\dots \frac{p_k}{4}=\frac{p_1 p_2\dots p_k}{4^k}$. Заметим, что вклад каждого простого в это произведение либо меньше (это хорошо!), либо больше (это плохо!) чем 1, в зависимости от того меньше $p_i$ чем 4 или нет. Но простых меньших 4 у нас всего-то раз, два и обчелся. Поэтому с ростом $k$$p_i$) объем работ у нас неизменно растет, хотя с маленькими простыми скорость роста меньше. Так как произведение простых у нас в районе $\sqrt{N}$ (см. выше), то объем работ примерно выражается формулой $\frac{\sqrt{N}}{4^k}$, и мы заинтересованы в росте $k$, а следовательно в выборе как можно меньших простых. Поэтому можно предполагать, что $p_1, p_2, \dots, p_k$ - это первые $k$ простых чисел в их естественном порядке.
Например, для 512-битного $N$ потребуется около 50 первых простых, что дает выигрыш (не считая накладных расходов!) всего лишь в $4^{50}=2^{100}$ раз по сравнению с тупым поиском делителей в отрезке $[2,\sqrt{N}]$, что соответствует суммарному количеству итераций порядка $N^{1/2-1/5} = N^{0.3}$. Для 1024-битного числа количество итераций будет уже $N^{0.35}$ и т.д.
В общем, игра не стоит свеч.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group