mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2018-12-24, 18:22   #1
datblubat
 
Dec 2018

210 Posts
Default Diamond multiplication and factorization method

I've found these two patent papers:
https://patents.google.com/patent/US20120066282A1/en
https://patents.google.com/patent/US20140207839A1/en

The authors claim that they have found a polynomial method of factorizing integer numbers.

I've read it carefully and the interesting thing is that the method of multiplication from the first one really works for any two odd numbers. I've even implemented it in C# and it seems correct.

I have never seen such a method before and it seems that every composite number has this diamond structure guided by "whole zeros". For two numbers of different bit size I just always put the smallest one on the left leaning side and prepend with zeros.

It works also for even numbers after removing trailing zeros from each number to make them odd, perform the operation, and then sum and add the removed zeroes to the product

The factorization however is not described really well here. I understand finding the complementary structure and I can see how it may work for small numbers - even on a piece of paper, but it seems when you try to project it back to two-dimensional diamond form it still involves some trial and error process that grows quickly in size, unless I don't understand it fully.

The second paper is some messed up 3D stuff, but It is almost the same method.

I don't know if this is something important, but I wanted to share just in case it is and I just don't understand it fully.
datblubat is offline   Reply With Quote
Old 2018-12-24, 18:46   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000012 Posts
Default

It just seems so unlikely to work, and the payoff is so small (because even if it turns out to be true, the method is patented), I can't be bothered to even look it over. All the more so since you looked at it and found it inscrutable.
CRGreathouse is offline   Reply With Quote
Old 2018-12-24, 19:51   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

106458 Posts
Default

Quote:
Originally Posted by datblubat View Post
I'm no expert on patents or patent law, but one thing jumped off the screen on both pages. They have the same notation (my emphasis):

Quote:
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Abandoned
Dr Sardonicus is offline   Reply With Quote
Old 2018-12-24, 20:23   #4
datblubat
 
Dec 2018

2 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
It just seems so unlikely to work, and the payoff is so small (because even if it turns out to be true, the method is patented), I can't be bothered to even look it over. All the more so since you looked at it and found it inscrutable.
I couldn't find any discussion about this particular method so I started one to establish if this is all garbage and I'd be glad if someone could look at it and share his/her thoughts.

1. It seems that multiplication method and the "diamond form" of every composite number is real thing.

2. The factorization method (poorly described) also work - you can "convert" from 1D binary form to 2D diamond form knowing N and it's N0 complement. but I'm not sure if and how it is faster than just trying every combination.

Quote:
Originally Posted by Dr Sardonicus View Post
I'm no expert on patents or patent law, but one thing jumped off the screen on both pages. They have the same notation (my emphasis):
Not sure if "abandoned" is equivalent to "our method doesn't actually work so we stop paying". Found one definition:
Quote:
Quote:
A patent becomes abandoned when the patent owner fails to pay the required maintenance fees to the United States Patent and Trademark Office.

Last fiddled with by datblubat on 2018-12-24 at 20:37
datblubat is offline   Reply With Quote
Old 2018-12-24, 21:56   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
the payoff is so small (because even if it turns out to be true, the method is patented)
Admittedly, Dr. Sardonicus' research does cut out this bit of my reasoning.
CRGreathouse is offline   Reply With Quote
Old 2018-12-24, 22:59   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×32×5×53 Posts
Default

Quote:
Originally Posted by datblubat View Post
I've found these two patent papers:
https://patents.google.com/patent/US20120066282A1/en
https://patents.google.com/patent/US20140207839A1/en


The factorization however is not described really well here. I understand finding the complementary structure and I can see how it may work for small numbers - even on a piece of paper, but it seems when you try to project it back to two-dimensional diamond form it still involves some trial and error process that grows quickly in size, unless I don't understand it fully.
I think the first patent has found a factorization method that is polynomial in N, rather than in the number of digits of N. It appears to my non-professional-mathematician-eye to be a really fancy trial division algorithm.
VBCurtis is offline   Reply With Quote
Old 2018-12-25, 17:29   #7
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90810 Posts
Default

Regardless of the merits or lack thereof in these patents, there are a lot of reasons why the patents would be abandoned. Sometimes it is purely monetary to help budgets. Sometimes the point was merely to have it protected for a limited time, and now it still works as a defensive publication. It's much cheaper to publish for defensive reasons in one of the boutique journals meant for that purpose, but often the company is undecided and might choose patent to be safe, then changes their mind. The engineers are almost never involved in that discussion.

I don't think you can read too much into this. I laugh every time I see the articles like "International Apple-Packard-Soft filed a patent on bird collars for rural WiFi - how will this affect next year's products? An in depth look at how the company is signaling a fundamental shift in direction." Um, no. Some engineer got a bonus for writing up an idea. Someone in legal tech thought it was worth looking into. More discussions and they decided it wouldn't hurt to file a patent, for all sorts of different possible reasons. Slog through the writing and filing process and there you go -- a patent that only 10 people in the company even know exists and no further work will ever be done on it.

Every now and then these sorts of things strike gold, or it turns out that rather silly patent has just enough overlap to be worth tossing into a bin of "we'll trade you these for all of those" or a "you sue us, we'll counter-sue with 32,767 patents we claim you're infringing." It turns out it is worth spending $50k each on some iffy patents, plus $5k each on a bunch of defensive publications and trade secrets, on the off chance that one of them will prevent a lawsuit that costs the company hundreds of millions. Or, as I witnessed a few times, was enough incentive for someone to work a little in their spare time and flesh out some ideas, some of which went into products and arguably were worth millions of dollars.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
improving factorization method bhelmes Computer Science & Computational Number Theory 7 2017-06-26 02:20
New factorization method henryzz Miscellaneous Math 4 2017-04-13 12:41
multiplication and logarithm bhelmes Math 4 2016-10-06 13:33
Possible better multiplication algorithm Triber Computer Science & Computational Number Theory 17 2015-11-10 17:48
Fast factorization method or crankery? 10metreh Factoring 6 2010-04-08 11:51

All times are UTC. The time now is 07:59.

Thu May 6 07:59:13 UTC 2021 up 28 days, 2:40, 0 users, load averages: 1.86, 1.77, 1.80

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.