Q:

How to license software that implements a well-documented algorithm, but which does not borrow source from the official library? 

I have implemented an RSYNC library based on the 
technical report by Andrew Tridgell and Paul Mackerras.   The library implementation does not borrow code from the official RSYNC library and does not conform to the official API.   I would like to release my library as free software on GitHub. 
The RSYNC library itself is released under the GNU GPL, but as I am not using or modifying the library's source, I am not sure how to license my own library.   What are my licensing options, if any?   How do I attribute the technical report? 

A:

Since you have never looked at the source code, and ONLY looked at:

The API
The no-code very high-level description of the synchronization algorithm

then you are free to release your implementation under any license you want. 
Just like SAMBA checked the API and algorithms of CIFS and released their software under the license they wanted. 
Or at least, that was the common point of view until the Google vs Oracle lawsuit, where the "structure, sequence and organisation" of an API got considered a copyrighted work and therefore copying the RSYNC API would be copyright infringement.  Google tried to appeal the appeal but the supreme court refused a few months ago.  I'm not sure if there will be further developments, but this decision is a huge loss for interoperability and innovation so we can only hope that the judiciary will realize their mistake. ( Thanks Abhi for the info)
You don't have to attribute the technical report (except if you pasted significant parts of it inside your code or documentation), but an URL is nice and safe to paste before each relevant algorithm implementation. 
In case you had seen the source code, the matter would not be so clear-cut, see some real-world examples with various outcomes at https://en.wikipedia.org/wiki/Clean_room_design#Case_law.