Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу Пред.  1, 2, 3
Автор Сообщение
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 01 апр 2016, 00:00 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
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) , используя алгоритм Евклида в Гауссовом кольце

В общем, все , как вы описали
Алгоритм вроде прост, но довести до ума его оказалось непросто, потому что арифметика у гаусса несколько отличается от обычной
арифметики :pardon:

Этот алгоритм разложения простого числа фантастически быстр
Например, составное число, состоящее из 1000 единиц, можно разложить на два квадрата и простое число вида 4k+1, которое в свою очередь состоит из 255 цифр, и раскладывается оно по этому алгоритму на два квадрата практически мгновенно:
3140070557972900385591457500338679835199029532195469823911097734599822535668450266239917735468356475798227473664359504753283045**2
+
1036194613595329967308688108308718219629667397158796393641927893608065243064767323532035391913612021913592662998148334087534694**2
==
109337423862922171408457758371736912144384262559170058452530326759411732036370155725
367378329013080578398265287191227457621314607648024484452045655760924358782054860014
63921297046807043750205006089890347895958918929145595801097543569716837316620538145661

Совершенно немыслимо найти эту комбинацию перебором

И основная проблема состоит не в том, чтобы разложить простое число, а в том, чтобы просто найти комбинацию из двух квадратов и простого числа вида 4k+1

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 01 апр 2016, 00:19 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Программа находит неимоверное количество разложений составного числа, состоящего из 1000 единиц, на 4 квадрата

Если взять в качестве испытуемого другое число, состоящее из 1031 единицы, которое является простым числом, оно также раскладывается на различные варианты из 4-х квадратом, не останавливаясь

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 02 апр 2016, 12:19 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Есть т.н. проблемные натуральные числа
Например, миллион нельзя разложить на два числа, одно из которых - квадрат, а другое - простое число вида 4k+1 или 8k+3
Миллион же нельзя разложить на три числа, два из которых - квадраты, а третье - простое число вида 4k+1 или 8k+3
И так чисел тьма

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 02 апр 2016, 15:55 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Не вижу здесь проблем.
Понятно, что если от числа вида 4k отнять два квадрата, то число вида 4k+1 никак не получится.
Но во-первых, числа вида 4k всяко лучше сначала поделить на 4.
Во вторых, можно искать разложение на сумму 2 квадратов плюс удвоенное простое.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
s_e_r_g
 Заголовок сообщения: Re: Проблема Варинга
СообщениеДобавлено: 02 апр 2016, 22:13 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Но во-первых, числа вида 4k всяко лучше сначала поделить на 4.
.


О, спасибо
Оказывается, мне как раз не хватало именно этого последнего штриха
Я сейчас запустил программу, которая раскладывает натуральные числа подряд, начиная с [math]10^{1000}[/math]
Смотрю на экран и не верю своим глазам - за одну секунду она успевает разложить несколько чисел
Она отмотала первую тысячу чисел подряд, и нет никаких признаков задумчивости

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу Пред.  1, 2, 3  Страница 3 из 3 [ Сообщений: 25 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Проблема

в форуме Алгебра

Dengi

4

393

27 дек 2015, 17:32

Проблема с ну

в форуме Дифференциальные и Интегральные уравнения

ExtreMaLLlka

1

427

18 янв 2016, 23:11

Проблема с размерностью

в форуме Механика

crazymadman18

2

251

16 май 2018, 20:37

Проблема с заданием

в форуме Дифференциальное исчисление

dastreba

8

329

28 ноя 2017, 19:00

Проблема с форматом wav

в форуме MATLAB

Apelcin_Espada

0

353

23 апр 2017, 10:27

Ряд Лорана проблема

в форуме Комплексный анализ и Операционное исчисление

danek130995

1

384

05 дек 2014, 20:38

Проблема с доказательством

в форуме Геометрия

Kristinadefa

1

345

05 окт 2015, 11:24

Проблема Гольдбаха

в форуме Интересные задачи участников форума MHP

maxleskoff

6

939

09 мар 2015, 11:34

Проблема с интегрированием

в форуме Интегральное исчисление

Nurbz

14

782

07 фев 2015, 17:53

Хьюстон. У нас Проблема

в форуме Алгебра

Kolob

7

234

17 дек 2021, 18:15


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved