Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 3 из 3 |
[ Сообщений: 25 ] | На страницу Пред. 1, 2, 3 |
|
Автор | Сообщение | |
---|---|---|
s_e_r_g |
|
|
swan писал(а): Еще раз: самое главное - научиться раскладывать простое на сумму 2 квадратов. Квадратичный невычет вы нашли. Какие сложности с алгоритмом Евклида? Допилил я ваш алгоритм Сначала я раскладываю число на два квадрата плюс простое число вида 4k+1 Затем я раскладываю простое число еще на два квадрата Алгоритм разложения простого числа состоит из следующих шагов 1. Нахожу [math]z^2 + 1 = 0 (mod p)[/math] 2. Находим квадратичный невычет [math]a^{(p-1)|2} +1 = 0 (mod p)[/math] 3. Находим [math]z=a^{(p-1)|4} = 0 (mod p)[/math] 4 Ищем НОД(p, z+i) , используя алгоритм Евклида в Гауссовом кольце В общем, все , как вы описали Алгоритм вроде прост, но довести до ума его оказалось непросто, потому что арифметика у гаусса несколько отличается от обычной арифметики Этот алгоритм разложения простого числа фантастически быстр Например, составное число, состоящее из 1000 единиц, можно разложить на два квадрата и простое число вида 4k+1, которое в свою очередь состоит из 255 цифр, и раскладывается оно по этому алгоритму на два квадрата практически мгновенно: 3140070557972900385591457500338679835199029532195469823911097734599822535668450266239917735468356475798227473664359504753283045**2 + 1036194613595329967308688108308718219629667397158796393641927893608065243064767323532035391913612021913592662998148334087534694**2 == 109337423862922171408457758371736912144384262559170058452530326759411732036370155725 367378329013080578398265287191227457621314607648024484452045655760924358782054860014 63921297046807043750205006089890347895958918929145595801097543569716837316620538145661 Совершенно немыслимо найти эту комбинацию перебором И основная проблема состоит не в том, чтобы разложить простое число, а в том, чтобы просто найти комбинацию из двух квадратов и простого числа вида 4k+1 |
||
Вернуться к началу | ||
s_e_r_g |
|
|
Программа находит неимоверное количество разложений составного числа, состоящего из 1000 единиц, на 4 квадрата
Если взять в качестве испытуемого другое число, состоящее из 1031 единицы, которое является простым числом, оно также раскладывается на различные варианты из 4-х квадратом, не останавливаясь |
||
Вернуться к началу | ||
s_e_r_g |
|
|
Есть т.н. проблемные натуральные числа
Например, миллион нельзя разложить на два числа, одно из которых - квадрат, а другое - простое число вида 4k+1 или 8k+3 Миллион же нельзя разложить на три числа, два из которых - квадраты, а третье - простое число вида 4k+1 или 8k+3 И так чисел тьма |
||
Вернуться к началу | ||
swan |
|
|
Не вижу здесь проблем.
Понятно, что если от числа вида 4k отнять два квадрата, то число вида 4k+1 никак не получится. Но во-первых, числа вида 4k всяко лучше сначала поделить на 4. Во вторых, можно искать разложение на сумму 2 квадратов плюс удвоенное простое. |
||
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: s_e_r_g |
||
s_e_r_g |
|
|
swan писал(а): Но во-первых, числа вида 4k всяко лучше сначала поделить на 4. . О, спасибо Оказывается, мне как раз не хватало именно этого последнего штриха Я сейчас запустил программу, которая раскладывает натуральные числа подряд, начиная с [math]10^{1000}[/math] Смотрю на экран и не верю своим глазам - за одну секунду она успевает разложить несколько чисел Она отмотала первую тысячу чисел подряд, и нет никаких признаков задумчивости |
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3 | [ Сообщений: 25 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Проблема
в форуме Алгебра |
4 |
393 |
27 дек 2015, 17:32 |
|
Проблема с ну | 1 |
427 |
18 янв 2016, 23:11 |
|
Проблема с размерностью
в форуме Механика |
2 |
251 |
16 май 2018, 20:37 |
|
Проблема с заданием
в форуме Дифференциальное исчисление |
8 |
329 |
28 ноя 2017, 19:00 |
|
Проблема с форматом wav
в форуме MATLAB |
0 |
353 |
23 апр 2017, 10:27 |
|
Ряд Лорана проблема | 1 |
384 |
05 дек 2014, 20:38 |
|
Проблема с доказательством
в форуме Геометрия |
1 |
345 |
05 окт 2015, 11:24 |
|
Проблема Гольдбаха | 6 |
939 |
09 мар 2015, 11:34 |
|
Проблема с интегрированием
в форуме Интегральное исчисление |
14 |
782 |
07 фев 2015, 17:53 |
|
Хьюстон. У нас Проблема
в форуме Алгебра |
7 |
234 |
17 дек 2021, 18:15 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |