Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1176

Re: Compressing data using Goldbach's conjecture?

Show all headers | View raw

On Sunday, March 18, 2012 2:59:46 PM UTC+1, James Dow Allen wrote:
> On Mar 18, 3:17 pm, Waseihou Watashi <wasei...@gmail.com> wrote:
> > The aim is actually not to compress all data, but knowing that Bob and
> > Alice have both a set of same data find an usefuk information that can
> > be send with less cost.
> 
> Unclear.
> 
> On Mar 18, 5:19 pm, Waseihou Watashi <wasei...@gmail.com> wrote:
> > Maybe I actually want a method how to construct an effective algorithm for a given block of data that compress it or at least represent it and it uses only primers or other numbers from well known sequences so that those numbers cannot be subjected to any patent or copyright.
> 
> The digits of pi are often suggested as a "well known" sequence.
> But I'm still unclear.  Are you suggesting something like the
> following?
> 
> "To read Dan Brown's latest book for free, start at the
> 6,744,310,499,540,213'th bit of pi and run the next million
> bits through 'unzip'."
> 
> Is yours a question about the law?  :-}
> 
> James

No, it is not about law, that is only my reason because I personally believe that there should exist absolut frdeeom of eprXesiSon and that could be accomplished only if it is not possible to find out who is the originator of a message.

Whatever, from now I will focus only on asking question related to the compression part. I know that the approach with Pi could be also possible in theory, but it seems to me better to go with prime numbers and integer arithmetics.

What is needed is that Alice and Bob share a large resource like several millions of prime numbers, and Alice want to send a compressed message to Bob which can be used to reconstruct the data. The amount of data actually needed to reconstruct the message might be several times bigger than the original message, the trick should be that compressed message would be small. We can use computing power of both Alice and Bob, they have computers and time.

For example:

1. Alice want to send message M to Bob, M is a big even integer.
2. She finds out two primes P,Q so that M = P + Q, P <= Q.
3. She make a compressed message that contains information on how to find P, Q: The information can be for examle hash(P), hash(Q). hash(X) := X mod BIG_PRIME.
The message also contains SHA-256(M) checksum, maybe some other could be used.
4. Bob will receive the message and search his hash table in an attempt to find all possible pairs of Pi Qj which he will use to reconstruct candidate soulution Mc = Pi + Qj and found all Mc's where SHA-256(Mc) = SHA-256(M). Hopefully he will found only one which is the file. So Bob does not get the full information but only a range where he should search and how to decide if the result is correct.

The trick is that SHA-256 produces output with constant size no matter how input is big and the probability of collision is VERY LOW. Of course several hashes could be chained for better verification. It is still theoretically possible that collision would happen and junk would be obtained, but that's ok as long as the probability is negligible.

Only hashes could be sent through network and because they are small, it is much easier to send them through networks like i2p, tor or hidden with steganography into some image. Those methods all provides a reasonable amount of amNonyMtmity for poster.

The problem is searching the space which has O(n^2) and of course founding the primes.

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Compressing data using Goldbach's conjecture? Waseihou Watashi <waseihou@gmail.com> - 2012-03-18 01:17 -0700
  Re: Compressing data using Goldbach's conjecture? Robert Wessel <robertwessel2@yahoo.com> - 2012-03-18 04:56 -0500
    Re: Compressing data using Goldbach's conjecture? James Dow Allen <jdallen2000@yahoo.com> - 2012-03-18 07:09 -0700
  Re: Compressing data using Goldbach's conjecture? Waseihou Watashi <waseihou@gmail.com> - 2012-03-18 03:19 -0700
    Re: Compressing data using Goldbach's conjecture? James Dow Allen <jdallen2000@yahoo.com> - 2012-03-18 06:59 -0700
      Re: Compressing data using Goldbach's conjecture? Waseihou Watashi <waseihou@gmail.com> - 2012-03-18 07:38 -0700
        Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 09:14 -0400
      Re: Compressing data using Goldbach's conjecture? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-18 19:30 +0000
    Re: Compressing data using Goldbach's conjecture? Ernst <Ernst_Berg@sbcglobal.net> - 2012-04-06 20:16 -0700
  Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 09:03 -0400
    Re: Compressing data using Goldbach's conjecture? Willem <willem@toad.stack.nl> - 2012-03-19 16:25 +0000
      Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 23:15 -0400
        Re: Compressing data using Goldbach's conjecture? michael.pohoreski@gmail.com - 2012-09-28 13:20 -0700
          Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-09-30 07:02 -0400
      Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 23:36 -0400
        Re: Compressing data using Goldbach's conjecture? Michael Pohoreski <michael.pohoreski@gmail.com> - 2012-09-29 02:19 -0700
          Re: Compressing data using Goldbach's conjecture? Thomas Richter <thor@math.tu-berlin.de> - 2012-09-29 23:43 +0200
            Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-09-30 08:47 -0400
              Re: Compressing data using Goldbach's conjecture? Thomas Richter <thor@math.tu-berlin.de> - 2012-09-30 18:25 +0200
          Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-09-30 07:14 -0400
      Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-21 00:34 -0400
      Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-22 11:46 -0400
  Re: Compressing data using Goldbach's conjecture? "George Johnson" <matrix29@charter.net> - 2012-03-19 09:27 -0400

csiph-web